SML is a strict (eager) language.
It is however possible to implement laziness in new datatypes.
- A lazy language such as
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
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 : unit -> 't nList).
The "by-need" optimisation is included:
If the closure is evaluated the result is saved in the cell,
and the saved value is used subsequently.
This optimisation requires the use of ref types.
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 *)
| 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 ()
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'
causes 5 tails to be evaluated and '
first 10 ns'
only causes a further 5 tails to be evaluated.
window on the wide world:|
| :: || cons |
| [x1,...] || list |
| [ ] || list |
| @ || append |
| fn => || &lambda . |
| : || has type |