[Ocaml-lib-devel] About iterators and enums

[Martin J. <mar...@em...>]

[inspired by discussions on caml-list]

On Wed, 28 Apr 2004, Nicolas Cannasse wrote:

> Please state clearly your problems on the ExtLib mailling list, I will be
> happy to think about theses :)
> Enums are still young so there not yet specialized enums that can  remove
> elements while itering or give random access. Maybe in the future...

Enum provides some kind of forward iterators (given the Enum.get
function) - and much more.

About iterators:
With arrays, it is natural to expect some bidirectional behavior, including
'slice' iteration, but of course this is impossible if it has type Enum.t.

Something nice could be done with objects:
Iterator.array would create an object with methods "previous" and
"next" while List.to_enum would provide only a "next" method.

[here, "next" and "previous" are equivalents of ++ and --; they do not
return a new iterator without modifying the original one]

let _ = List.iter (fun obj -> obj#next) [ int_array_enum; int_list_enum ]


A similar approach could be used without objects, like this:

let (next_a, copy_a) =
  Iterator.Backward.array ~first: 3   [| 0; 1; 2; 3; 4; 5 |];;

let (next_b, copy_b) =
  Iterator.Forward.list [ 0; 1; 2; 3 ];;



Here is the test:

let print next_a next_b =
  try
    while true do
      Printf.printf "%i %i\n" (next_a ()) (next_b ())
    done
  with Iterator.End -> ()

let _ =
  let (next_a', _) = copy_a () in
  let (next_b', _) = copy_b () in
  ignore (next_a ());
  print next_a next_b;
  print next_a' next_b'



The output is:

4 0
3 1
5 0
4 1
3 2


I attach the full code.
Compile with -rectypes:

  ocaml -rectypes test_iterator.ml


I was happy to play with this... However I am not convinced about
the usefulness of iterators in OCaml.
I think that it could be an interesting approach in some cases, like the
example about graphs that was posted: for recording the current position
in the iteration. This requires some memory allocation.

Efficiency matters, and this is why higher order functions seem
preferable in most cases.

Some additional remarks:

1) Hashtbl.enum works in O(n), is this allowed?

2) The implementation of Hashtbl.keys is terribly inefficient:

  let keys h = Enum.map (fun (k,_) -> k) (enum h)

Why not:

  let list_keys h = fold (fun key data accu -> key :: accu) h []
  let enum_keys h = List.enum (list_keys h)

3) Why making every module depend on Enum?
I think that Enum should provide conversion functions from/to more basic
containers. In the standard lib, there are Array.to_list and Array.of_list
because lists are more important than arrays.
Since Enum provides a super container, I think it would be more natural
to make it depend on the core containers such as lists, arrays, and other
things that could be implemented independently from Enum.
Then Enum would have to define Enum.of_list, Enum.of_array and so on...
and I would avoid its use over mutable data, except in the very specific
cases of fixed length arrays and strings.


Martin