• Karen Lanrap (41/41) Nov 08 2006 Those recent discussions about dropping elements of arrays and
• Ary Manzana (25/70) Nov 08 2006 "foreach" shouldn't be the powerful one here: the iterator (or opApply)

Karen Lanrap <karen digitaldaemon.com> writes:

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.

Ary Manzana <ary esperanto.org.ar> writes:

Karen Lanrap escribió:
 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!

"foreach" shouldn't be the powerful one here: the iterator (or opApply) 
must be it.

It's just to write:

---
foreach(Element e; collection) {
}
---

instead of the longer and harder to understand

---
for(Iterator!(Element) it = collection.iterator(); it.hasNext(); ) {
	Element e = it.next();
}
---

Of course, "foreach" assumes member "iterator()" as default, but it 
should also be able (and it's posible in D) to do things like:

---
foreach(Element e; collection.preorder()) {
}

foreach(Element e; collection.postorder()) {
}

etc.
---

It's just give you a shorter, cleaner notation, that integrates well 
also with arrays. At least that's how it works in other languages.