dropping elements of arrays and other simplistic views on foreach (rant, long)

Karen Lanrap karen at digitaldaemon.com
Wed Nov 8 03:02:14 PST 2006


Those recent discussions about dropping elements of arrays and 
'linearizing' structures are more connected than the participants 
of those discussions seem to believe.

A simple example:
Binary trees can be implemented quite easily in arrays by defining 
that the childs of a node located in cell i of the array are 
located in the cells 2*i and 2*i+1. Under such a scheme the root of 
the tree is located in cell 1 of the array.

As everyone should know, there are at least three canonical 
traversals of binary trees: preorder, postorder and inorder.

How can those three traversals correspond to those two foreach: 
"foreach" and "foreach_reverse"?

Right, there is no way. But those foreach correspond to tree 
traversals.

If the cells of an array are viewed as a compressed representation 
of a path in a tree from the root to a leaf, then "foreach" 
corresponds to a preorder traversal and "foreach_reverse" 
corresponds to a postorder traversal or, at the option of the 
reader, to an inorder traversal, because both yield the same result 
on pathes.

Combining this facts implies that only two "foreach" chracteristics 
are not enough:

D needs at least
    foreach(preorder),
    foreach(inorder) and
    foreach(postorder)
where "foreach" is a short hand for "foreach(preorder)".

This generalization must be extended for trees with higher degree.

For trinary trees there are two positions to compute an inorder 
traversal on the current node: after visiting the leftmost child or 
before visiting the rightmost child.

In general: for an n-ary tree there are n+1 canonical traversals.

In other words: the current implementation of "foreach" has far too 
few characteristics!

Note: this only handles trees with known bounds on their degree. If 
D wants to support linearizing of arbritray structures more 
characteristics seems to be needed, as I pointed out in
http://www.digitalmars.com/pnews/read.php?
server=news.digitalmars.com&group=digitalmars.D&artnum=43763

Further Note: as shown, there is no canonical way to drop cells of 
arrays.



More information about the Digitalmars-d mailing list