[Camllist] generic programming

Oleg
 Johan Baltié

Ketanu

Chris Hecker
 Oleg
 Peter Wood
 John Max Skaller
 Francois Pottier

Chris Hecker
 Jun P.FURUSE
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Francois Pottier <francois.pottier@i...> 
Subject:  Re: [Camllist] 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 (heapallocated) structure has to be used. It is defined below. Note that it is essentially a list of (element, righttree) 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 worstcase constant time, since it may have to travel arbitrarily far down the current subtree's left spine. However, it does work in amortized constant time; in other words, iterating over a complete tree still takes worstcase 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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners