Tree as nested list
Eric
could use struct::tree from Tcllib, but I was tempted by "Trees as
nested lists" (http://wiki.tcl.tk/8580). However, as far as I can see,
that won't work if there is a node with only one child which also has
only one child.
My real question is, how do I tell the difference between
{{z}} and {z} and z using the list commands. I know the string representations
are different, but I'm don't think there will be a reliable way to do
that either.
TIA
Eric
Neil Madden
Tagged lists are perhaps a better way of doing this kind of thing. You
can make simple "algebraic datatypes" easily enough:
# Constructor constructor
proc cons {name args} { proc $name $args { info level 0 } }
# Simple tree data type:
# Tree a = Leaf a | Branch (Tree a) (Tree a)
cons Leaf val
cons Branch left right
% set tree [Branch [Branch [Leaf 1] [Leaf 2]] [Leaf 3]]
Branch {Branch {Leaf 1} {Leaf 2}} {Leaf 3}
You can then write traversals etc:
# foldtree :: (a -> b -> a) -> a -> Tree b -> a
proc foldtree {f z tree} {
switch -exact [lindex $tree 0] {
Leaf { set z [invoke $f $z [lindex $tree 1]] }
Branch {
set z [foldtree $f $z [lindex $tree 1]]
set z [foldtree $f $z [lindex $tree 2]]
}
}
return $z
}
proc invoke {cmd args} { uplevel #0 $cmd $args }
# Count the number of leaves in a tree
proc count {sum _} { incr sum }
foldtree count 0 $tree ;# => 3
# Sum the tree
proc + {a b} { expr {$a + $b} } ;# Or use tcl::mathops::+
foldtree + 0 $tree ;# => 6
etc. The foldtree can be converted to a more efficient iterative version
too.
-- Neil
Aric Bills
children} (or {nodevalue children} if you don't need to distinguish
node name from node value):
The tree:
node1 (value1)
|
+-node2 (value2)
| |
| +-node3 (value3)
|
+-node4 (value4)
Can be represented:
{node1 value1 {{node2 value2 {{node3 value3 {}}}} {node4 value4
{}}}}
This method is more "verbose", but it has the distinct advantage of
not confusing node values with tree structure.
Having said all that, the struct::tree package is excellent; I would
recommend you not reinvent that wheel unless you have a really
compelling reason to do so.
tom.rmadilo
> I need to serialise some trees, so that I can reconstruct them later. I
> could use struct::tree from Tcllib, but I was tempted by "Trees as
> nested lists" (http://wiki.tcl.tk/8580). However, as far as I can see,
> that won't work if there is a node with only one child which also has
> only one child.
>
Are you saying you have something which works, and you want something
else? If you have something that works, the answer is: use it.
> My real question is, how do I tell the difference between
> {{z}} and {z} and z using the list commands. I know the string representations
> are different, but I'm don't think there will be a reliable way to do
> that either.
You are wrong in thinking that there is a difference. In general, you
can't tell the difference between a string and a list, it depends 100%
on the command that you apply to the string/value.
Eric
No compelling reason, this is just the (probably common) case of being
frightened by the struct::tree man page, and looking for something
"simpler", only to find out that it isn't :) .
E
Eric
Thanks very much. Time once again to be amazed by what Tcl can do (if
your mind works the right way to let you think of it!). Though I don't
think I will use it for the current problem - my trees aren't binary for
a start (I know there's a mapping to binary, but that's another level of
complication).
E
Eric
> On Apr 26, 7:35 am, Eric <e...@deptj.demon.co.uk> wrote:
>> I need to serialise some trees, so that I can reconstruct them later. I
>> could use struct::tree from Tcllib, but I was tempted by "Trees as
>> nested lists" (http://wiki.tcl.tk/8580). However, as far as I can see,
>> that won't work if there is a node with only one child which also has
>> only one child.
>>
>
> Are you saying you have something which works, and you want something
> else? If you have something that works, the answer is: use it.
>
See my answer to Aric Bills.
>> My real question is, how do I tell the difference between
>> {{z}} and {z} and z using the list commands. I know the string representations
>> are different, but I'm don't think there will be a reliable way to do
>> that either.
>
> You are wrong in thinking that there is a difference. In general, you
> can't tell the difference between a string and a list, it depends 100%
> on the command that you apply to the string/value.
>
I'm not surprised that there is no difference, I just hadn't thought
about it before. And it does mean that the code on that wiki page will
not work as-is for "linear" trees.
E
Neil Madden
General trees are also easily made:
# Tree a = Leaf a | Branch [Tree a]
cons Leaf a
cons Branch args
proc foldtree {f z tree} {
switch -exact [lindex $tree 0] {
Leaf { set z [invoke $f $z [lindex $tree 1]] }
Branch {
foreach x [lrange $tree 1 end] {
set z [foldtree $f $z $x]
}
}
}
return $z
}
set tree [Branch [Leaf 12] [Branch [Leaf 4]] \
[Branch [Leaf 6] [Leaf 9]]]
-- Neil
tom.rmadilo
As Neil points out with this example, a 'tree' is really more than a
data structure. It usually includes procedures or methods to create,
manipulate and maintain the tree in memory. But it also is usually
associated with some serialized representation which can be 'written'
out as text.