[MLton-user] Iterator

[Stephen Weeks]

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