Terrence asked:
> How good is J with tree-like hierarchical data?
This is a hard question to answer, because it depends on the definition of
"how good".
Boxes are a general data structure, and can represent trees. For example:
5!:2{.;:'toJ'
+-------------------------------+--+------------------------------+
|+-+-------------------------+-+|@:|+-----+----------------------+|
|| |+---------------------+-+|]|| ||+-+-+|+--+-+---------------+||
|| ||+---------------+-+-+|}|| || |||#|~|||-.|@|+---------+-+-+|||
|| |||+--+-+--------+|@|]|| || || ||+-+-+|| | ||+--+-+--+|@|,||||
|| ||||I.|@|+--+-+-+|| | || || || || || | ||| |&|E.|| | ||||
|| |||| | ||e.|&| ||| | || || || || || | ||+--+-+--+| | ||||
|| |||| | |+--+-+-+|| | || || || || || | |+---------+-+-+|||
|| |||+--+-+--------+| | || || || || |+--+-+---------------+||
|| ||+---------------+-+-+| || || |+-----+----------------------+|
|| |+---------------------+-+| || | |
|+-+-------------------------+-+| | |
+-------------------------------+--+------------------------------+
5!:4{.;:'toJ'
+- 10{a.
| +- I.
| +- @ -+ +- e.
+-+- } ----- @ -+ +- & ------+- 13{a.
| | +- ]
| +- ]
-- @: -+
| +- ~ ----- #
| |
+-+ +- -.
| | +- 13 10{a.
+- @ ---+ +- & -+- E.
+- @ -+- ,
That said: J doesn't provide many convenient tools for manipulating boxes
as trees. There are {:: L. L: S: but there is still no }:: .
Further, I find L: S: inadequate and frustrating in many cases.
Another approach is to represent trees in lists. For example, a binary tree
can be stored in an list which maintains certain relationships among
indicies:
http://en.wikipedia.org/wiki/Binary_tree#Methods_for_storing_binary_trees
I'm pretty sure this can be generalized to other types of trees, and J's
sparse arrays may alleviate the space-wasting problem normally associated
with trees-as-lists. Also, keeping the data unboxed might provide speed
advantages.
But both approaches share the same problem: you can do it, but you have to
do it yourself. J does not provide native tools to work on trees.
J's fundamental, and only, data structure is the rectangular array. Its
tools are oriented to work on that structure. For one thing, trees are
rarely processed en masse; they require lots of small decisions and focus on
small pieces, and J is designed to be fast when processing large chunks
("thinking big").
OTOH, J is making advances in this field. For example, deeply nested
structures used to be unbearably slow, even with trivial operations. But
Roger fixed that in 6.01:
http://www.jsoftware.com/help/release/bxref.htm
We used to also be limited by stack depth, but 6.01 also raised that limit:
http://www.jsoftware.com/help/release/recurlim.htm
which, combined with the new adverb M. eases the former disincentives of
recursive algorithms (though the latter currently only memoizes scalar
integers).
Perhaps the biggest advance was dyadic ;: . FSM is useful for problems
which historically been difficult or slow in J (i.e. scalar, "loopy"
algorithms that make lots of small decisions). For example, Roger's:
http://www.jsoftware.com/jwiki/Essays/Huffman_Coding
(or the related Lab) demonstrates efficient tree processing in J.
-Dan
PS: I see no reason to worry about linked lists in J, in other languages
those are primarily used to implement dynamic ("growable") arrays, e.g.
java.util.Vector. There are no static arrays in J (well, maybe jmf).
--
View this message in context:
http://www.nabble.com/How-good-is-J-with-tree-like-hierarchical-data--tf4915841s24193.html#a14078795
Sent from the J General mailing list archive at Nabble.com.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
