Re: [Caml-list] Re: generic programming

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

On Wed, Jul 03, 2002 at 10:29:09AM -0700, Chris Hecker wrote:
>
> "Sure. I have a 'problem' example: try to implement STL iterators
> in Caml. I don't have the expertise in Caml: I think this requires
> 'higher order functors'. Several people have attempted this, no one
> has succeeded that I know of."

My memories of STL are vague, but if an iterator is what I think it
is, then implementing one in O'Caml is pretty straightforward. An
iterator is a function that returns a function which maintains a
piece of internal state. There is certainly no need for functors
here!

Here is one for lists:

(* [iterator s] returns a stateful iterator over the list [s]. That is,
   if $s = \{ x_1, x_2, \ldots, x_n \}$, then [iterator s] is a function
   which, when invoked for the $k^{\text{th}}$ time, returns [Some ]$x_k$,
   if $k\leq n$, and [None] otherwise. *)

(* val iterator : 'a list -> (unit -> 'a option) *)

  let iterator list =

    let remainder = ref list in

    let rec next () =
      match !remainder with
      | [] ->
	  None
      | elem :: rest ->
	  remainder := rest;
	  Some elem in

    next

And (more interesting) here is one for trees:

(* [iterator s] returns a stateful iterator over the tree [s]. That is, if
   $s = \{ x_1, x_2, \ldots, x_n \}$, where $x_1 < x_2 < \ldots < x_n$, then
   [iterator s] is a function which, when invoked for the $k^{\text{th}}$
   time, returns [Some ]$x_k$, if $k\leq n$, and [None] otherwise. Such a
   function can be useful when one wishes to iterate over a tree's elements,
   without being restricted by the call stack's discipline.

   Because the call stack is not used to store information about which part
   of the tree remains to be walked, an explicit (heap-allocated) structure
   has to be used. It is defined below. Note that it is essentially a list
   of (element, right-tree) pairs, which corresponds to the information
   which would be stored in the call stack, if it were used.

   It would be possible to implement a straightforward iterator by first
   turning the tree into a list, then walking the list. Our implementation
   is more economical, because it only allocates a structure of size $O(\log
   n)$ (the call stack) at a given time, and because only one walk is
   necessary, thus reaping a small constant time factor. *)

(* val iterator : 'a list -> (unit -> 'a option) *)

  type 'a tree =
    | Empty
    | Node of 'a tree * 'a * 'a tree * int

  type 'a remainder =
    | Nothing
    | ElemThenRightThenParent of 'a * 'a tree * 'a remainder

  let iterator s =

    (* When asked to create an iterator for s, we allocate a piece of state,
       which shall allow the iterator to remember which part of the tree
       remains to be walked. It consists of a tree and a remainder, which are
       to be walked in order. At first, the whole tree [s] has to be walked,
       and there is no remainder.

       Note that [next] does not work in worst-case constant time, since it
       may have to travel arbitrarily far down the current sub-tree's left
       spine. However, it does work in amortized constant time; in other
       words, iterating over a complete tree still takes worst-case linear
       time. *)

    let tree = ref s
    and remainder = ref Nothing in

    let rec next () =
      match !tree, !remainder with
      | Empty, Nothing ->
	  None
      | Empty, ElemThenRightThenParent (elem, right, parent) ->
	  tree := right;
	  remainder := parent;
	  Some elem
      | Node(l, v, r, _), parent ->
	  tree := l;
	  remainder := ElemThenRightThenParent(v, r, parent);
	  next () in

    next

I hope this helps,

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