On Mon, Sep 8, 2014 at 11:56 AM, Dan Bron <[email protected]> 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 >
The first link at the bottom of this wiki page --- http://dl.acm.org/citation.cfm?doid=166197.166231 --- looks interesting. It sounds like people have already thought about the tree problem in J and attempted to solve it. Has anyone read the paper? Does anyone have a public version of the article to share? > [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." <[email protected]> > Date: Sat, 6 Sep 2014 09:06:38 -0700 > To: [email protected] > > 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
