Proposal for fix-typed recursive array

[wolfgang371]

Motivation: while this works in crystal...

a = [1,2,3,[4,5]]

... the following does not work (but does in ruby):

a = [1,2,3]
a.push([4,5,6])
a.push(7)
p a # -> => [1, 2, 3, [4, 5, 6], 7]

Moreover, both is not available in a flexible way in crystal for instance/class variables since they need to have a fixed type.

So I tried to come up with something generic. Since this is not absolutely straightforward to me and to my knowledge not yet available in the crystal lib, maybe you want to add something like this?

class RecursiveArray(Type)
    property value : Type | Array(RecursiveArray(Type))

    def initialize # empty
        @value = [] of RecursiveArray(Type)
    end
    def initialize(value : RecursiveArray(Type))
        @value = value.value
    end
    def initialize(value : Type | Array(RecursiveArray(Type)))
        @value = value
    end
    def initialize(value : Array(Type)) # syntactic sugar, supports e.g. RecursiveArray(Int32).new([1,2,3])
        @value = value.map {|el| RecursiveArray(Type).new(el).as(RecursiveArray(Type))}
    end
    def initialize(value) # syntactic sugar; supports e.g. RecursiveArray(Int32).new([1,[2,3]])
        @value = from_a(value).value
    end
    # push always pushes only _one_ element (vs. concatenation of arrays)
    def push(el : RecursiveArray(Type))
        if v = @value.as?(Array(RecursiveArray(Type)))
            v.push(RecursiveArray(Type).new(el.value))
        end
    end
    def push(el : Type | Array(RecursiveArray(Type)))
        if v = @value.as?(Array(RecursiveArray(Type)))
            v.push(RecursiveArray(Type).new(el))
        end
    end
    def push(value : Array(Type)) # syntactic sugar
        if v = @value.as?(Array(RecursiveArray(Type)))
            v2 = value.map {|el| RecursiveArray(Type).new(el).as(RecursiveArray(Type))}
            v.push(RecursiveArray(Type).new(v2))
        end
    end
    def [](index : Int32)
        if v = @value.as?(Array(RecursiveArray(Type)))
            v[index]
        else
            raise("foo")
        end
    end
    private def from_a(value)
        if value.is_a?(Type)
            res = RecursiveArray(Type).new(value)
        else
            res = RecursiveArray(Type).new
            value.each {|el| res.push(from_a(el))}
            res
        end
        res
    end
end

Some tests:

class MyTest
    @x : RecursiveArray(Int32)
    def initialize
        # basic
        @x = RecursiveArray(Int32).new(1)
        @x = RecursiveArray(Int32).new([RecursiveArray(Int32).new(2),RecursiveArray(Int32).new(3)])
        p @x[0].value # -> 2

        # RecursiveArray
        @x = RecursiveArray(Int32).new([RecursiveArray(Int32).new(1), RecursiveArray(Int32).new([RecursiveArray(Int32).new(2),RecursiveArray(Int32).new(3)])])
        @x.push(4)
        @x.push([RecursiveArray(Int32).new(5)])
        p @x[1][0].value # -> 2

        # sugar
        @x = RecursiveArray(Int32).new([1,2,3])
        @x.push([4,5,6]) # very much like ruby
        @x.push(7) # dito
        # p @x.value # #value is best to access _leaf_ values
        p @x[3][2].value # -> 6

        @x = RecursiveArray(Int32).new
        @x.push(1)
        @x.push([2,3,4])
        p @x[0].value # -> 1
        p @x[1][1].value # -> 3

        @x = RecursiveArray(Int32).new([1,2,3,[4,5]])
        p @x[3][1].value # -> 5
    end
end

MyTest.new

BTW: first I tried something based on alias (https://crystal-lang.org/reference/syntax_and_semantics/alias.html) but then I learned on the one hand side they might get thrown out again (#5155) and on the other had some troubles on my first experiment based on the provided example.

Another note: I also tried to implement the complementary method to_a. But then I realized this is not possible with crystal as it is since this already makes the compiler break:

def x
    res = [1]
    1.times do # this loop already breaks compilation
        res = [1, res]
    end
    res
end

p x

[Blacksmoke16]

FWIW the first example works if you correctly type the array. E.g.

a = [1,2,3] of Int32 | Array(Int32)
a.push([4,5,6])
a.push(7)
a # => [1, 2, 3, [4, 5, 6], 7]

Otherwise the type of a is inferred from the values as Array(In32), not Array(Int32 | Array(Int32)).

[wolfgang371]

Yes, I know.
But nevertheless whatever concrete type(s) you specify you will never have full freedom (as e.g. with ruby). Supposedly you want to use also Array(Array(Int32)) you have to add that etc.

[Sija]

@wolfgang371 yeah, that exact limitation pushed me into creating any_hash shard, which allows pretty dynamic (and type recursive) manipulation - downside of that is the need to cast the returned values to the original type... perhaps you'll find some inspiration there, if not please ignore this message ;)

[Blacksmoke16]

@wolfgang371 It's my understanding that that would never work because Crystal isn't dynamically typed. So it's kinda expected you'd have to manually define the type of your ivars, e.g. Array(Array(Int32)). I.e. unless you use a custom type like you created, there just isn't a way to express a : ArbitrarilyNestedArray(Int32).

Of which, I think that would be best suited to a shard.

[straight-shoota]

What's the use case anyway?

[wolfgang371]

As for use cases: I use the arbitrary ruby arrays e.g. for trees or tree like data structures.

[wolfgang371]

@Blacksmoke16 (#10461 (comment) above): since in ruby this is part of the language the shard idea somehow was a blind spot to me.
So if you don't see a general merit in it, I will probably follow your idea then.

[straight-shoota]

I use the arbitrary ruby arrays e.g. for trees or tree like data structures.

Kay, that's a use case but IMO not a good one. Using generic, nested arrays for this isn't really a good idea. Neither in Crystal nor Ruby, but Ruby lets you get away with it. Maybe that's okay for Ruby.

But in Crystal you're way better of just using a special data type to represent an actual tree. Your RecursiveArray is such a type. But I don't think it belongs in stdlib. There are many ways to implement such a data structure and different use cases ask for different implementations. Unlike Array which is for very broad use cases, any tree implementation is more specific and less commonly useful.