Note that J already supports trees. After all, that's what directories are, and J supports directories (albeit using foreigns).
As for the efficiency of trees, well... you can see for yourself, from first hand experience. Operating systems, after all, have many many years of effort which have gone into making them "more efficient". Thanks, -- Raul On Mon, Sep 8, 2014 at 11:56 AM, Dan Bron <j...@bron.us> wrote: > I do think trees, if we did it right (that is, treated as first class > citizens in their own right, as opposed to a subtype or a different > perspective on "arrays"), would be a powerful extension to the language. > That would take some serious thought, though: for one thing, trees, by > their nature, encourage "thinking little" (or at least are applied in > situations where such thinking is called for); that is, making numerous, > "small", and frequently independent decisions, as you travese their > branching structures. > > Such methods are in direct (diametric) contrast to traditional array > programming, which encourages and rewards thinking big (and treating all > elements as equally, as citizens, rather than uniquely, as individuals). > In concrete terms, we would have to, at the very least, extend or > introduce tree-specific primitives, and make sure their definitions are in > harmony with the existing "array" primitives, and prevailing philosophy of > J. No small thing (and, by implication, we'd have to permit our mere > mortal selves the heresy of modifying scripture: Ken's Dictionary would > have to be changed). > > Anyway, in eons past, I once started collecting my ideas about trees in J, > their relationship to boxes, other potential ways how to represent them, > obstacles to including them as a datatype, and how they might (or not) fit > into J's design. Unfortunately I never got very far with the project, but > I did draft an initial writeup on the Wiki, if you're interested (though > overall the writeup, as it stands, has a fairly defeatist, negative tone > on the applicablity of trees in J; a stance which is pragmatic given the > current status of J, but certainly not final; if we put our backs into it, > we could get this done). > > -Dan > > [1] Old thoughts on the question of trees in J: > http://www.jsoftware.com/jwiki/DanBron/Temp/Tree > > [2] Though the Wiki article above links to it, it's worth calling out > specifically Devon's summary of "A Programming Lanaugage"'s proposal for > trees. > http://www.jsoftware.com/jwiki/DevonMcCormick/APLTree > > > ----- Original Message --------------- > > Subject: [Jprogramming] Ragged Array Shapes are Trees > From: "Michal D." <michal.dobrog...@gmail.com> > Date: Sat, 6 Sep 2014 09:06:38 -0700 > To: programm...@jsoftware.com > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
