I think trees are done at least ok, if not "right" already.
I think Michal might be thinking of reinventing the box. I view trees as lists
of lists, where the right hand side of "of" might as well be anything including
subtrees.
So tree's are inherently polymorphic, and even if limited to only one other
datatype, include lists/trees of that datatype.
While there is no perfect generic tree structure to suit all needs, a
featureful single-data-type generic tree structure can be created in any
language by tracking "parent, next sibling, and first child" for every node
(index) in your uni-datatype list.
I think in the end though, that J's nested box structure ends up being more
intuitive in many operations. L: and S: are extremely powerful.
I think }:: is a needed feature, just for the compatible indexing to monad {::
though I present
hook =: 2 : '([: u v) : (u v) '
amendT =: 2 : ' u hook (n { ]) n} ]'
10 + each each amendT 0 each amendT 1 (0 ;<(< i.5);i.4)
┌─┬──────────────────────────┐
│0│┌────────────────┬───────┐│
│ ││┌──────────────┐│0 1 2 3││
│ │││10 11 12 13 14││ ││
│ ││└──────────────┘│ ││
│ │└────────────────┴───────┘│
└─┴──────────────────────────┘
10 + amend 2 each each amendT 0 each amendT 1 (0 ;<(< i.5);i.4)
┌─┬──────────────────────┐
│0│┌────────────┬───────┐│
│ ││┌──────────┐│0 1 2 3││
│ │││0 1 12 3 4││ ││
│ ││└──────────┘│ ││
│ │└────────────┴───────┘│
└─┴──────────────────────┘
while it seems complicated, each use of "each" creates an open after selecting
from right to left. It provides a way to update trees with a verb
----- Original Message -----
From: Dan Bron <j...@bron.us>
To: programm...@jsoftware.com
Cc:
Sent: Monday, September 8, 2014 11:56 AM
Subject: Re: [Jprogramming] Ragged Array Shapes are Trees
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
