Hi Michal,
maybe this is an interesting representation for what you want?
([:|. $ ;~ $ each) (i. 2 3) ; (,0) ; 0 1
┌─┬─────────┐
│3│┌───┬─┬─┐│
│ ││2 3│1│2││
│ │└───┴─┴─┘│
└─┴─────────┘
----- Original Message -----
From: Michal D. <michal.dobrog...@gmail.com>
To: programm...@jsoftware.com
Cc:
Sent: Saturday, September 6, 2014 12:06 PM
Subject: [Jprogramming] Ragged Array Shapes are Trees
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
