[Axiom-math] Re: [fricas-devel] Re: [open-axiom-devel] [fricas-devel] Re: [fricas-devel] Re: [fricas-devel] Re: iterators and cartesian product.

[Gabriel Dos Reis]

On Wed, 24 Oct 2007, Bill Page wrote:

|                                                 But converting a
| domain (Product) to a List just to iterate over it seems like a waste
| and is still less economical. I would like the compiler to make this
| operation transparent and more efficient.

Iteration is an old topic -- did I say that SIMULA had coroutines?
This problem has been studied to depth, with lots of solutions.  As
Waldek would say, a variety of solutions is an indication that
opinions are split over which is better.

I do fully agree that it does not make much sense, from efficiency
point of view, to make a list just be to able to iterate over elments
of Product.  There are various solutions to that problem.  One being
generartors -- or coroutines or semi-coroutines.  Another, quite
effective, is the notion of `iterator' in used the C++ Standard Template
Library. 

   http://www.sgi.com/tech/stl/

It relies on semantics description of iterators, along with hierarchical
categorisations of algorithms and containers bases on complexity and
semantics description of iterators.  Note that STL is the result of a
long term project, some of the earlier description may be found here

  http://www.stepanovpapers.com/

Basically, a domain that whish to be iterated over provides two
operations -- begin() and end() -- that people use to initiate/end
iteration over data structures.  That does not require coroutines.
It can be made to work in Spad if we had good support for nested
domains. 

Now, you may say that you really want begin() and end() to be implicit
in some cases, that can be made to work too -- just like generate() is
implicitly called in Aldor.  For C++, there is a well-advanced
proposal for C++0x to make that work:

    vector<int> v;
    // ...
    for (int x: v)
       // ...

would be roughly equivalent to

    for (auto p = v.begin(); p != v.end(); ++p) {
       int x = *p;
       // ...
    }

Notice that this solution, when applied to BinaryTree, does not
require one to first construct a List and then iterate, and finally
throw it away.  One caniterate over BinaryTree without recursion.

-- Gaby