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 14:31, Radu Grigore wrote:
> The
> difference is that after you write the iterators code for a new
> sequence-like data structure all the "generic" functions, not only
> fold but also map and others, will automagically work on them.

I think this is the core of what we disagree on. I believe you'll be 
implementing a new data structure (e.g. splay trees) because you want to use 
different algorithms under the hood so that you get different asymptotic 
complexities for different operations. Therefore, the "automagically" 
generated ones will be useless because they'll have terrible performance - 
they'll need replacing.

The different functions (e.g. insert, find for a splay tree) require 
completely different algorithms so iterators are useless. For example, "find" 
on a "set" in the STL does not use iterators. Equivalently, the HOF fold is 
useless, e.g. "find" in "Set" in OCaml does not use fold:

let rec fold f s accu = match s with
  Empty -> accu
| Node(l, v, r, _) -> fold f l (f v (fold f r accu))

The similar functions (e.g. accumulate for a splay tree) do have commonality 
which can be factored out. This commonality is factored out as functions 
templated over iterators in the STL. In OCaml, this can be factored out by 
writing these functions in terms of fold:

let sum fold c = fold ( +. ) 0. c
let list_sum = sum List.fold_left

The automagic effect will only be worthwhile if you are implementing a lot of 
data structures (which is very unlikely) in which case you can use a tuple of 
functions:

let common fold =
  (fun fold c -> fold ( +. ) 0. c),
  ...
let list_sum, list_... = common List.fold_left

> You should really check out the article cited by Vasili. It seems that
> we understend different things by "functional equivalent of an
> iterator",

I read it yesterday and, indeed, we did not mean the same thing by that term. 
I was referring to how I would go about rewriting a C++/iterators program in 
OCaml. I wouldn't begin by implementing iterators. I think you were referring 
to how iterators could be implemented in a functional language. Is that 
right?

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