## digitalmars.D - dropping elements of arrays and other simplistic views on foreach (rant,long)

• 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
server=news.digitalmars.com&group=digitalmars.D&artnum=43763

Further Note: as shown, there is no canonical way to drop cells of
arrays.
```
Nov 08 2006
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.
```
Nov 08 2006