Home     About     Download     Resources     Contact us

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Browse thread
[Caml-list] generic programming
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Francois Pottier Subject: Re: [Caml-list] Re: generic programming
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