Standard ML doesn't have built-in support for lazy evaluation. Some implementations, notably SML/NJ, have nonstandard lazy evaluation primitives, but programs that use those primitives won't be portable. Lazy suspensions can also be implemented in a portable manner, using Standard ML's module system.
First we define an interface, or signature, for manipulating lazy suspensions:
signature LAZY = sig type 'a lazy val pure : 'a -> 'a lazy val delay : ('a -> 'b) -> 'a -> 'b lazy val force : 'a lazy -> 'a exception Diverge val fix : ('a lazy -> 'a) -> 'a end
This signature indicates that:
-- Haskell, not Standard ML! xs :: [Int] xs = 1 : xs
After defining the interface, we have to provide an actual implementation, also known as module or structure:
structure Lazy :> LAZY = struct datatype 'a state = Pure of 'a | Except of exn | Delay of unit -> 'a type 'a lazy = 'a state ref fun pure x = ref (Pure x) fun delay f x = ref (Delay (fn _ => f x)) fun compute f = Pure (f ()) handle e => Except e fun force r = case !r of Pure x => x | Except e => raise e | Delay f => (r := compute f; force r) exception Diverge fun fix f = let val r = ref (Except Diverge) in r := compute (fn _ => f r); force r end end
This structure indicates that a suspension is internally represented as a mutable cell, whose internal state is one of the following:
Pure x, if the suspension was already forced, and its final result is
Except e, if the suspension was already forced, and an exception was thrown in the process.
Delay f, if the suspension wasn't forced yet, and its final result can be obtained by evaluating
Furthermore, because we used opaque ascription (
:>), the internal representation of the type of suspensions is hidden outside of the module.
Here's our new type of lazy suspensions in action:
infixr 5 ::: datatype 'a stream = NIL | ::: of 'a * 'a stream Lazy.lazy (* An infinite stream of 1s, as in the Haskell example above *) val xs = Lazy.fix (fn xs => 1 ::: xs) (* Haskell's Data.List.unfoldr *) fun unfoldr f x = case f x of NONE => NIL | SOME (x, y) => x ::: Lazy.delay (unfoldr f) y (* Haskell's Prelude.iterate *) fun iterate f x = x ::: Lazy.delay (iterate f o f) x (* Two dummy suspensions *) val foo = Lazy.pure 0 val bar = Lazy.pure 1 (* Illegal, foo and bar have type `int Lazy.lazy`, * whose internal representation as a mutable cell is hidden *) val _ = (foo := !bar)