Proposal: Hide the int in opApply from the user

[bearophile]

Bill Baxter>In other words, the author seems to have overlooked the other place where state can be stored: on the stack.<

In other parts of that article the author is aware of the stack too, he talks about the alloca() function too.
What I don't like is the formatting of those snippets of C code :-)

void maptimes(fn,limit) void (*fn)(int); int limit;
{int i; for (i=0; i<limit; i++) (*fn)(i);}

The article presents some problems of iterating on a collection, and how to solve them in Lisp, C and C++. The main problems are:
1) Iterating on a collection
2) Given a collection (like a tree), enumerate the Cartesian product of it with itself.
3) Given two collections, like two trees, find if they have the same leaves, ignoring the other structure of the tree. The purpose is to do this computation efficiently, keeping the collection data encapsulation, etc.
4) I think the article tries to talk about a problem where you need to do both 2) and 3).

Putting an opApply method into the collection class is enough to solve the 1) and 2) problem too.

The problem 3) can be solved in many ways, the simpler way is to scan both trees to accumulate their leaves into an array, and then to see if the two (or more) arrays are equal. But that ways usually wastes too much memory and time if the trees aren't small. So a lazy approach is better. In Haskell and in recent versions of Python it's easy to perform lazy computations. (In Python you can write a function/method generator, that yields the leaves, then you just have to write a little function that calls the two generators in parallel. If the two generators give equal sequences, and they stop at the same time, then the two trees have the same fringe). The D opApply doesn't allow you to do that, I presume (fibers/threads may help, but so far I haven't used them to solve this problem of parallel lazy scan).

But to solve the samefringe problem in D (if you have a Tree data structure class) you can add three methods to that class, like "next", "isfinished" and "reset" (or something similar) that use a little part of the state of the tree object to iterate on the nodes, where the "next" method gives the currently seen node. Then you can write a little function that calls "next" on two different trees, to solve the samefringe problem (so you need "next", "isfinished", "reset" to solve parallel scan problems, and you can add "opApply" method too, for a faster single scan, because I presume opApply is faster than using the next/isfinished pair).

To solve the problem 4) (that's not stated in the article, I think) the reset/next/isfinished methods don't suffice, because the object stores just one iteration state. So you may need to give the tree class yet another method that returns a newly created object with reset/next/isfinished methods and a new iteration state. This is probably closer to the solution used by C++ (but it's a friend class, not a nested class). You may want to avoid putting the reset/next/isfinished methods in the tree class, and just use this smaller iteration object for the problem 3) too.

I don't know if D may use some standard way (like opApply) to allow parallel lazy scans (that is to manage the yield like Python does).

I am learning D still, so if you see something wrong, silly or non D-thonic among the things I have written here, please tell me :-)

Bye,
bearophile