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

[Ary Manzana]

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.