|
|
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 : 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 *)
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'
causes 5 tails to be evaluated and 'first 10 ns'
only causes a further 5 tails to be evaluated.
|
www #ad:
SML:
| :: | cons |
| [x1,...] | list |
| [ ] | list |
| @ | append |
| fn => | &lambda . |
| : | has type |
Compared
|
|
|