Perhaps a way forward is to pursue your idea of comparing and contrasting
how different implementations of trees look in realistic scenarios.
Though this does not directly lead to a notation, it may shed some light on
what a good notation would handle.
On Tue, Sep 9, 2014 at 11:50 AM, Dan Bron <j...@bron.us> wrote:
> Yes, the most obvious candidates for #tree are maximum depth (or
> breadth), # leaves, or # total nodes. There are others, but the ones I can
> think of are less compelling.
>
> What I was trying to underscore with my message is there are, in fact,
> multiple definitions available for #tree , all with unique, competing,
> benefits and drawbacks, but ultimately we can only choose one, and once
> we choose one, we can't go back.
>
> So if we're going to seamlessly integrate trees, as a distinct (non-box)
> datatype in J, we're going to have to consider how they'll be used, and
> which definition is "the best". I, personally, don't feel qualified to
> make that decision (especially since we'll have to ensure all new
> defintions or extensions are philosophically harmonized with existing
> definitions as they apply to rectilinear arrays).
>
> In other words: this (seamless integration of trees in J) is a worthy
> objective, but not an easy one to achieve. Personally, I'd be happy to
> contribute to such an initiative, but I lack the self-confidence to lead
> it.
>
> -Dan
>
>
> ----- Original Message ---------------
>
> Subject: Re: [Jprogramming] Ragged Array Shapes are Trees
> From: "'Pascal Jasmin' via Programming" <programm...@jsoftware.com>
> Date: Tue, 9 Sep 2014 07:16:46 -0700
> To: "programm...@jsoftware.com" <programm...@jsoftware.com>
>
> L. might be a candidate. (depth)
> # of leaves (boxes) might be the most popular ([: +/ 1: S:0)
> When a tree holds nested records (say customers invoices products bought),
> then the # of records could be defined as just # .
> You might want to know number of invoices, but can't naively use L: because
> a customer might also have nested phone numbers or other data. The point
> of this blabbering is that sometimes # is domain specific.
>
>
>
>
> ----- Original Message -----
> From: Dan Bron <j...@bron.us>
> To: programm...@jsoftware.com
> Cc:
> Sent: Tuesday, September 9, 2014 9:24 AM
> Subject: Re: [Jprogramming] Ragged Array Shapes are Trees
>
> Here's a question to chew on. What's the # of a tree?
>
>
> ----- Original Message ---------------
>
> Subject: Re: [Jprogramming] Ragged Array Shapes are Trees
> From: "Michal D." <michal.dobrog...@gmail.com>
> Date: Mon, 8 Sep 2014 23:04:34 -0700
> To: programm...@jsoftware.com
>
> Thanks for the links, they make for interesting reading.
>
> I agree that the elegance of the solution is the hard part. Nevertheless
> there have been previous attempts at ragged arrays that we can potentially
> learn from: nested arrays in APL and K to some degree. I was hoping to
> find out more about the various approaches that have come up in the past.
>
> It's interesting to me that the restriction that one places on what type of
> ragged arrays are allowed is also exactly the type of raggedness required
> for representing a shape of such an array (this is an observation not a
> fact):
>
> 1) Arrays are rectangular : a rectangular rank-1 array is enough to
> describe the shape.
>
> 2) Arrays are rectangular except for the last dimension : the shape can be
> represented by a rank-2 array with singleton entries for the leading axes
> and a rank-1 array describing the size of each last dimension.
>
> 3) Arrays are arbitrarily ragged : the shape can be represented as a tree
> (ie. a boxed or arbitrarily ragged array).
>
> Cheers,
>
> Mike
>
> On Mon, Sep 8, 2014 at 10:54 AM, Dan Bron <j...@bron.us> wrote:
>
> > I expand on this in a little more detail in the Wiki page I linked to,
> but
> > (in my view), there are two aspects to address w.r.t. trees in J;
> > efficiency is one of the two questions, but the less interesting one
> > ("efficiency is a SMOP" [1]).
> >
> > The other, more interesting question, is "convenience". Is it convenient
> to
> > create, address, manipulate and process trees -- qua trees, not in the
> > guise of orthotopic arrays -- in J? And I mean "convenient" in the way
> > creating, addressing, manipulating and processing orthotopic arrays is
> > "convenient" in J. Are trees convenient in J? Short answer: no.
> >
> > Solution? Language (re-)design.
> >
> > Anyone want to volunteer for the task of making tree programming as
> > seamless, elegant, beautiful, and (to steal a phrase from Alan Perlis)
> > lyrical in J as array programming?
> >
> > -Dan
> >
> > [1] SMOP:
> > http://www.catb.org/jargon/html/S/SMOP.html
> > (tongue-in-cheek, though I do believe "redesign the language" makes
> > "improve the performance of trees" seem easy by comparison.)
> >
> >
> >
> > ----- Original Message ---------------
> >
> > Subject: Re: [Jprogramming] Ragged Array Shapes are Trees
> > From: Raul Miller <rauldmil...@gmail.com>
> > Date: Mon, 8 Sep 2014 12:00:05 -0400
> > To: Programming forum <programm...@jsoftware.com>
> >
> > 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
> > ----------------------------------------------------------------------
> > 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
>
> ----------------------------------------------------------------------
> 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
