# [MLton-user] Iterator

Stephen Weeks sweeks@sweeks.com
Thu, 4 Mar 2004 19:29:54 -0800

```> I'd like to program an iterator/coroutine/lazy list - I have a data
> structure and want to provide a list-like interface to the contents, but
> the list elements should only be generated on demand.
>
> What's the most *efficient* way to do this in MLTon?  I couldn't find
> direct support for lazy evaluation.  The continuation docs mention time
> proportional to stack size, which looks nasty.  Should I use threads?  Or
> am I making life too complicated and should I code something directly
> using a mutable reference (I'm used to programming in Haskell, so that
> last thought only just occurred to me, but I'm guessing it's the way to
> go)?

You could use threads, which won't be as slow as continuations, but
that's probably overkill, and will still be a lot slower than function
calls.  My bet is the right thing to do is to reify the stack
yourself.  As an example, consider the following code that converts a
tree to a sequence.

--------------------------------------------------------------------------------
structure Seq =
struct
datatype 'a t = T of unit -> ('a * 'a t) option

val dest: 'a t -> ('a * 'a t) option =
fn (T f) => f ()

fun empty (): 'a t = T (fn () => NONE)
end

structure Tree =
struct
datatype 'a t =
Empty
| Node of {left: 'a t,
right: 'a t,
value: 'a}

fun toSeq (t: 'a t): 'a Seq.t =
let
fun force (t: 'a t, rest: 'a Seq.t): ('a * 'a Seq.t) option =
case t of
Empty => Seq.dest rest
| Node {left, right, value} =>
force (left,
Seq.T (fn () => SOME (value, delay (right, rest))))
and delay (t: 'a t, rest: 'a Seq.t): 'a Seq.t =
Seq.T (fn () => force (t, rest))
in
delay (t, Seq.empty ())
end
end
--------------------------------------------------------------------------------

If you need, you can make the resulting sequence lazy by memoizing the
thunk in delay with a mutable reference.  It depends on the complexity
of the data structure and how many times you walk the sequence as to
whether that's worth it.

```