[Jprogramming] APL2007 pictures -> Guy Steele's keynote

[Roger Hui]

http://www.jsoftware.com/jwiki/Essays/Quicksort  has an example of trees.



----- Original Message -----
From: Raul Miller <rauldmiller at gmail.com>
Date: Monday, December 3, 2007 4:44
Subject: Re: [Jprogramming] APL2007 pictures -> Guy Steele's keynote
To: Programming forum <programming at jsoftware.com>

> On Dec 2, 2007 11:47 PM, Devon McCormick <devonmcc at gmail.com> 
> wrote:> However, upon reading the section in "A Programming 
> Language" dealing with
> > trees, it looks as though  trees are represented by using 
> matrixes.  A directed
> > graph is shown represented as a boolean matrix with a one in 
> the row and
> > column where node "row number" goes to node "column
> > number".
> 
> You can also represent a tree using flat lists -- with a list of
> integers representing
> structure  (for each node, the index of the parent node, 
> with some special value
> representing the root node) and a parallel list representing 
> node data.
> 
> Of course, these representations work best for operations 
> performed on the tree
> as a whole, and work poorly for scalar operations on 
> trees.  But that tends to
> be true with J and APL overall.
> 
> Put differently, if trees are being used to optimize scalar 
> processing, you
> probably should not be trying to copy this approach in J -- you 
> would do
> better working from first principles (perhaps using a small 
> cache of recent
> changes represented against some larger archive structure, or perhaps
> doing something completely different...).
> 
> However, I can also see trees represented in J using boxed lists.
> This could be a boxed structure of indices into some flat clump 
> of data
> (which you would need to carefully manage so updates use special
> code).  Or, for keyed trees, you might want to maintain a 
> pair of
> parallel boxed lists (one of indices and the other of 
> keys).  In all
> cases you should have fairly shallow trees with fat nodes.  And
> I think you would have to be using explicit coding for at least some
> critical operations.
> 
> That said, I do not feel like coding up any examples at the moment,
> in part because this subject is so broad that specific examples
> might not be interesting, but also because I have no immediate
> uses for trees.