30

Ruby supports recursive arrays (that is, self-containing arrays):

a = []
# => [] 
a << a
# => [[...]] 
a.first == a
# => true

This is intrinsically cool, but what work can you do with it?

sawa
  • 165,429
  • 45
  • 277
  • 381
hoffm
  • 2,386
  • 23
  • 36
  • 3
    Note that this example is easy, since `a.first` and `a` are exactly the same object (same `object_id`). Ruby supports comparison of independent recursive structures too (e.g. `b = []; b << b; a == b # => true`). – Marc-André Lafortune Sep 07 '12 at 13:53

2 Answers2

42

A directed graph with undifferentiated edges could have each vertex represented simply as an array of the the vertices reachable from that vertex. If the graph had cycles, you would have a 'recursive array', especially if an edge could lead back to the same vertex.

For example, this graph:
directed cyclic graph
...could be represented in code as:

nodes = { a:[], b:[], c:[], d:[] }
nodes[:a] << nodes[:a]
nodes[:a] << nodes[:b]
nodes[:b] << nodes[:a]
nodes[:b] << nodes[:c]
p nodes
#=> {:a=>[[[...], []], [...]], :b=>[[[...], [...]], []], :c=>[], :d=>[]}

Usually the representation of each vertex would be more 'robust' (e.g. a class instance with properties for the name and array of outgoing edges), but it's not impossible to imagine a case where you wanted a very lightweight representation of your data (for very large graphs) and so needed to use a minimal representation like this.

Phrogz
  • 296,393
  • 112
  • 651
  • 745
  • But what application does this possibly have? – Simpleton Sep 06 '12 at 21:40
  • 2
    @Simpleton What applications do [directed graphs](http://en.wikipedia.org/wiki/Directed_graph) have? Lots! Route finding; [establishing a hierarchy of cell-based formulae dependencies](http://phrogz.net/traversingdirectedgraph) to name two. – Phrogz Sep 06 '12 at 21:51
  • Cannot you do the exact same thing in just about any language that supports reference elements in lists? – inger Nov 27 '13 at 21:23
  • @inger Yes, of course. Recursive, self-referential data structures are certainly not limited to Ruby. That just happened to be what the OP was asking about. – Phrogz Nov 27 '13 at 21:28
8

Ruby supports recursive arrays

To me the question is why should it not support it?

An Array is simply a collection of references. Should it check each element and throw an error if one of the refers to the collection itself, so prevent recursion or using it for graphs like Phrogz' example.

So I don't think it's a feature, but if it would be, most languages I know has it, even Java.. Just use Object as Array elements.

inger
  • 19,574
  • 9
  • 49
  • 54
  • 4
    I'm not aware of another language besides Ruby that strongly supports recursive arrays. For example, I don't think you can compare two distinct recursive arrays in any other language. In Ruby: `a = []; a << a; b = []; b << b; a == b # => true` – Marc-André Lafortune Sep 07 '12 at 13:48
  • 2
    @Marc-André right that's an interesting corner-case, not sure who many other languages have _that level_ of support. Looking at the question/example I was (mis?)interpreting the OP's notion of 'support' as it allows you _creating_ recursive arrays - which most language does AFAIK. – inger Sep 09 '12 at 22:18