Re: Boost algorithm library (Was: [boost] New upload: algorithm.zip 1)

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-07-26 18:14:50

Vesa Karvonen wrote:
> 
> From: "Fernando Cacciola" <fcacciola_at_[hidden]>
> > From: Jeremy Siek <jsiek_at_[hidden]>
> [...]
> > I am not sure if a *standarized* container-like interface will have a good
> > impact on a program design.
> 
> I'm not so sure. Functional languages do quite well without iterators. Take a
> look at functions such as 'foldr', 'map', 'filter', 'take', 'drop', 'rev',...
> that you can find in most functional languages (in some functional languages
> they may be named differently).

        I don't really agree. First, lets call these functions
'functional iterators'. Lets take map as an example. The general form is

        map function list

Note that Fish 2 is the only language I know of in which map is 
polymorphic on the data functor (Charity?) The dual, or control inverted
stateful construction is just

        iterator

(where ++ goes to the next element, and * does the mapping).
In C++, such iterators are polymorphic on the data functor
in the ad hoc (overloading) sense.
 
You can do things with the C++ iterator you can't with the functional
one,
such as use it inside a callback: in the functional case, 
'function' IS a callback. 'function' is a slave of 'map', whereas 
for a stateful iterator the iterator is a slave of the algorithm:
hence the term 'control inversion'.

There is a big difference with current languages between the
two forms: the stateful iterator is unquestionably more powerful.
The reason is that it is trivial to implement the functional
map using an iterator (transform?), but almost completely impossible to
do the converse.

Note that stateful iterators are destructors, and they work
on coinductive (stateful) types like streams NOT inductive 
types like lists. Thats why the stateful list iterators
provided in many functional languages:

        head (first element of list)
        tail (rest of the list)

are incorrectly typed. (head doesn't make any sense 
for the empty list: streams are infinite, and so head
always works: head is a stream operator, NOT a list operator).
[The only correct way to destroy an inductive type is
with pattern matching]

The big advantage of the functional iterators is that they're
guarranteed to operate correctly in the sense that if 
they're type correct, they terminate and yield a 
result of the correct type.

The C++ iterator doesn't offer any such absolute guarrantee:
correctness depends on additional requirements
(such as begin++ ++ ++ ++ .. ++ == end, for some finite
number of ++'s)

> I don't see anything that
> could not be done with such a container reference, but could be done with a
> pair of iterators to a container.

        Of course not. They're isomorphic:

        tuple<it1, it2>

is the isomorphism. however, there are algorithms that require
several iterators, for example copy requires three iterators:
they're no way to model that with a containers only model.
 
> As a related issue, there are often very good reasons for providing an
> enumeration interface like this:
> 
>     struct not_primarily_a_container
>     { struct functor

        Argghh. You've got FP experience. Stop calling first class
functional objects functors! List is a data functor. Class templates
are functors. Functional objects are not functors!

> instead of an STL-style iteration interface. The choice between
> active/external and passive/internal iteration should be a conscious decision.

        Exactly! Better: it should be transparent. The SAME code
should work in both cases: we need coroutines, NOT subroutines.
I don't know how to do it. See Charity. This is the benchmark,
it comes closer to seamless integration of functional and
stateful programming than anything else.

        Both style of iterators are wrong. What we actually
want is something like:

        iterator { 
                //do stuff
                yield value; // return value
                //do stuff
                yield value;
        }

which can be used like a C++ iterator: when you say

        *++iterator

the routine is run until it yields a value, the
next call causes it to run until it yields
the next value. This way the client is the master
and the iterator the slave --- from the clients
view point. From the iterator writers viewpoint,
the iterator is the master, and the client
the slave (yield effectively calls the client
with the value).

I have seen this implemented in Metaware C++.
Note that it ONLY implements input iterators!

In FP terms, we're talking about using continuation passing:
that seems to be the closest to meeting the seamless
integration requirement.

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net