This is a very natural way of expressing trees in J. And, this shows some of the pain of using trees - no one tends to like any particular tree implementation. The grass is always greener on the other side of the fence.
(And the "point" of trees often seems to be mediocrely efficient - defining a complex incremental update mechanism as a way of avoiding thinking about the application of that mechanism or as a way of disproving the generality of some assertion, or whatever. Or, rather, redefining efficiency as "efficiency at micromanagement".) Oh well... -- Raul On Mon, Sep 8, 2014 at 1:35 PM, Devon McCormick <devon...@gmail.com> wrote: > "The best is the enemy of the good" > > I have J code that uses trees which I run daily and have been doing so for > years. The simple and efficient way I handle trees - using an idea from > APL days - is outlined here: > http://www.jsoftware.com/jwiki/DevonMcCormick/Trees . > > The code I run daily - which parses information about all the files on my > disk (using multiple cores in parallel) into some useful vectors - can be > seen here: > http://www.jsoftware.com/jwiki/DevonMcCormick/code/DirectoryParsing . Most > of the time is spent reading in the file information but, on my machine at > work, it builds the vectors, including the tree structure of the directory, > in about 100 seconds for over half a million files in almost 54,000 > directories, comprising almost 162 GB. This same process used to take 10 > or 15 minutes before I got SSDs on this machine. > > > > 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 >> > > > > -- > Devon McCormick, CFA > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
