Laziness
SML is a strict (eager) language. It is however possible to implement laziness in new datatypes.
- A lazy language such as λ or Haskell can accept a definition such as
- nonNegInts = Cons 0 (map (λ n.n+1) nonNegInts)
- -- meaning [0, 1, 2, 3, ...]
- but a strict language, such as SML, will reject it because the
RHS,
`Cons...nonNegInts)' must be evaluated before the binding to the LHS is made, that is before nonNegInts is defined.
The following example shows a well-known technique
to implement lists having non-strict tails.
The tail is computed by a closure
(a function
exception nListException of string;
datatype 't nList =
nCell of 't (* head strict, not by-need *)
* ('t nList option ref) (* tail, if eval-ed *)
* (unit -> 't nList) | (* closure for tail *)
nNil; (* else empty *)
fun nCons h t = nCell (h, ref NONE, t);
fun nHd (nCell (h, _, _)) = h
| nHd nNil = raise nListException "nHd nNil";
fun nTl (nCell(_, ref (SOME t), _)) = t (* tail eval-ed, or... *)
| nTl (nCell(c' as (_, _, t))) = (* ...not, so... *)
let val v = t() (* ...eval tail and... *)
in #2(c') := SOME v; (* ...memo it *)
(* print " eval "; *) (* trace *)
v
end
| nTl nNil = raise nListException "nTl nNil";
(* -----------------------------------------------------------test-- *)
fun from n = (* n, n+1, n+2, ... *)
let fun f n () = nCons n (f (n+1))
in f n ()
end;
fun first 0 nl = [] (* : int -> 't nList -> 't list (ordinary list) *)
| first n nl = nHd nl :: first (n-1) (nTl nl);
(*e.g.*) val ns = from 0; (* 0, 1, 2, 3, ... *)
first 5 ns; (* [0, ..., 4] *)
first 10 ns (* [0, ..., 9] *)
(* (tail-)by-need lists, `nList' LA, CSSE, Monash .au, 20/6/2005 *)
|
It is possible to make the head of the list non-strict by the same technique.
If the tracing print is uncommented and the example run,
it is seen that first 5 ns'first 10 ns'