Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Jon Harrop <jon@jdh30.plus.com>]

On Monday 27 September 2004 11:50, Radu Grigore wrote:
> On Mon, 27 Sep 2004 02:59:43 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> > What is the difference between a generic function and a function which
> > dispatches to appropriate specialised functions?
>
> For the client of the function there is no difference.
>
> For the writter of the function there is a big difference, especially
> if it has to write the specialized versions.

The equivalent to the writer of fold is the writer of an iterator. You have to 
write specialized versions for each type of iterator just as you would have 
to write your own fold.

Check out vector<T>::iterator and set<T>::iterator. Consider writing a splay 
tree in C++ using iterators. You would have to rewrite most of what's in the 
STL for "set" by hand...

> The good news is that the 
> OCaml library gives you those specialized functions (fold) for common
> data structures like List and Array. The bad news is that you are on
> your own if you define new data structures that can be viewed as
> sequences.

Right, like Set, which has a completely different fold to array and list. 
Equivalently, the implementations for vector, list and set iterators in C++ 
will be completely different. I don't think iterators buy you anything.

> The meaning of "fold" is "apply this function repeatedly for each
> element of the data-structure and accumulate the result". I'd like to
> be able to write this in code _once_ for every data-structure that can
> be seen as a sequence (i.e. a set of totaly ordered elements).

Why not write fold once "for every data structure..." seeing as they have next 
to nothing in common?

> You can 
> do this with iterators. As the article cited by Vasili shows there is
> an analogue of iterators in functional languages.

Presumably the benefit of iterators in a functional language would be 
bidirectional traversal of a sequence container. But iterators fall apart on 
general trees, matrices and anything which isn't just a sequence of elements. 
In many such cases you want mapi...

> So we are not really talking here about
> differences between OCaml and C++; we are talking about library
> design.

I think we are, because I think iterators are only really useful in an 
imperative setting. Hence C++ programmers use them extensively but OCaml 
programmers do not. Folds are simply not feasible in C++. I'm sure Stepanov 
would have reinvented them if they had been... ;-)

On Monday 27 September 2004 13:14, skaller wrote:
> Except you have to write:
>  let List.mapmap g f x = List.map g (List.map f x)
>  let Array.mapmap g f x = Array.map g (Array.map f x)

No, you don't have to write that. You can write a generic function which 
accepts a map as an argument:

let map_2 map f g c = map f (map g c)

or better still, the deforested:

let map_2 map f g c = map (fun x -> f (g x)) c

You can't write map_n without some jiggery pokery though.

> ...
> A generalised fold doesn't require either a sequence or any
> ordering

Folds with a particular direction are much more useful, IMHO. Hence the folds 
in the core library are left or right for arrays and lists and up for sets 
and maps.

> -- it just applies to all the elements of a container 
> in any order (so it works for a tree too).

A lexicographically ordered traversal can be defined for any data structure in 
OCaml - that's how hash and compare work.

Cheers,
Jon.

-------------------
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