Em Qui, 2009-02-19 às 22:57 +1100, Timothy S. Nelson escreveu:
> Interesting. I'm happy to assume that $root is allowed to be
> Undefined, I think. But let me ask a question; were you to represent an
> unrooted tree in a computer, how would you do it so that, if you had to look
> around the tree, you could do it? You'd need some node that was an
> entry-point into the tree. That's the purpose I'm trying to get at here.
Not at all, that is the same as saying that a list must always be
ordered, and that it should have a beggining. Circular Lists are very
well known.
If you think in a BTree, for instance, you usually don't have a root
node, since a BTree is simply a way to view a list, and you might
receive a node and work only from that context onward. That even applies
for filesystems: what if your process calls (2)chroot? what happens to
the "root" node?
On the other hand, I have to disagree with masak that it would be an
empty role, because there is indeed one operation that you can always do
in a tree node:
role Tree::Node {
method List lookup(*%options);
}
on a BTree you would have
$node.lookup(:left);
$node.lookup(:right);
on a Filesystem you would have
$node.lookup(:name<foo.txt>);
$node.lookup(:name<..>);
$node.lookup(:parent);
$node.lookup(:root);
$node.lokoup(:absolute</tmp/foo.txt>);
on a match object
$node.lookup(:hiearchy</named/token/with/subtokens>);
on a XML document you would have
$node.lookup(:xpath<somexpathexpression>);
$node.lookup(:attribute<foo>);
# of course, DOM would be a complementary API.
Where it could be spec that
$node.lookup()
should return all the child elements as a lazy list, which means that a
generic tree traversal could be written (and maybe the tree transforming
sub-language).
daniel
