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.

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.