Take a look at "From Trees into Boxes" on this page: http://sigapl.org/articles.php .
On Tue, Sep 9, 2014 at 10:06 AM, Thomas Costigliola <tcost...@gmail.com> wrote: > 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 > > > > 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." <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 > -- Devon McCormick, CFA ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
