Re: [Caml-list] Re: generic programming

[Francois Pottier <francois.pottier@inria.fr>]

On Fri, Jul 05, 2002 at 01:18:17AM +1000, John Max Skaller wrote:
> 
> Only two data structures in Ocaml readily admit iterators: lists and arrays.
> Other data structures like hastables, sets, maps, etc, have control
> inverted iterators, which are much weaker (that is, you have to provide
> a callback which is given each value in turn

This is true, and I might add that they are *intended* to be weaker.
Programming with an explicit `iter' or `fold' is much more structured
than using an iterator; it is more compact and makes your intent more
apparent. (This idiom is perhaps difficult to read for non-functional
programmers, but the same is true of many features in many languages.)

I find that the use of iterators is very seldom necessary. One typical
instance is when you need to simultaneously iterate over two trees
which have the same fringe, but not necessarily the same shape. Then,
you may use `iter' to iterate over one tree, but need an iterator to
traverse the other. I think this kind of situation arises rather seldom.

Lastly, I should insist (as shown in my previous posting) that this is
not a language issue; it's a library issue. O'Caml's standard library
offers stack-based iterators, but no stateful iterators. This design
choice is meant to encourage a functional programming style and I support
it.

> The real problem for STL style iterators is this: in C++,
> the very point of iterators is that container independent
> algorithms can be written. There is no easy way to do this in Ocaml,
> at least not without using classes.

This is wrong... why classes? (read on)

> are known as data functors). Hence, we have
> 
>     List..map
>     Array.map
>     Hashtble.map
> 
> etc, instead of just 'map' .

Certainly, but you can parameterize your code over `map' (that is, write
as a higher-order function or as a functor) and then apply it to a version
of `map' for the particular data structure at hand.

> Functorial polymorphism can be implemented for a wide class
> of functors in an extension of ML: there is work being done
> by Barry Jay at UTS on this.

As far as I understand, this work is about automatically *generating* code
for `map' from the definition of a data type, which is another issue. O'Caml
as it stands already allows you to write `container independent' code.

> Perhaps some of the type theorists reading the above text can give
> a better and more proper explanation. But basically: C++ allows
> polymorphism over data functors, but that polymorphism is NOT
> parametric like it should be.

Entirely true. I call that textual polymorphism :)

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners