Trees are an abstraction. Conceptually speaking all arrays - even non-ragged - can be thought of as trees. Whether they are very flat trees (only one level deep) or very tall and skinny trees (only one child at each node) or whether they are something else is not pre-determined.
And that's the problem with trees - or the benefit - there are so many possibilities to choose from. It usually helps to have a problem you are interested in solving, to help you make reasonable choices from all those possibilities. With those cautions out of the way, here's a small exploration of a tree traversal in J: http://rosettacode.org/wiki/Tree_traversal#J Thanks, -- Raul On Sat, Sep 6, 2014 at 12:06 PM, Michal D. <michal.dobrog...@gmail.com> wrote: > I just came to the realization that ragged array shapes, regardless of how > you want to represent them, are trees. I would be interested in any > references to prior exploration of this idea. > > Some example data (boxes are used to display ragged arrays, but otherwise > have no semantic meaning): > > ] A =. i. 2 3 > 0 1 2 > 3 4 5 > ] B =. (< @ i."0) 1+i.2 > +-+---+ > |0|0 1| > +-+---+ > ] C =. A ; B > +-----+-+---+ > |0 1 2|0|0 1| > |3 4 5| | | > +-----+-+---+ > ] D =. A ; < B > +-----+-------+ > |0 1 2|+-+---+| > |3 4 5||0|0 1|| > | |+-+---+| > +-----+-------+ > > The corresponding shape trees (monospace font required, root node is on the > left): > > A: 2 - 3 > > 1 > / > B: 2 > \ > 2 > > 2 - 3 > / > C: 3 - 1 > \ > 2 > > 2 - 3 > / > D: 2 1 > \ / > 2 > \ > 2 > > In some sense the shape tree for A is compressed, the verbose alternative > being: > > 3 > / > A: 2 > \ > 3 > > Compressing D in a similar manner leaves the full shape of the tree > ambiguous - there is no way to distinguish the duplicate structure of leaf > 3 from the structure of leaves 1, 2. > > 3 > / > D: 2 - 2 - 1 > \ > 2 > > We could resolving this ambiguity by listing the shapes of all the items > explicitly. The problem here is that 'compression' could very easily lead > to an increase in representation size, although it is nice and uniform for > ragged arrays of uniform rank. > > 3 > / > | 3 > | / > D: 2 - 2 + > | \ > | 1 > \ > 2 > > Regardless of compression, I would be interested in prior work in > representing shapes of ragged arrays as trees. > > Cheers, > > Mike > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
