Laziness

 FP  SML   SML97    Laziness Also see:  λ   e.g.   Intro  Haskell

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.

window on the wide world:
 The Darwin Awards V: Next Evolution

 Linux  Ubuntu free op. sys. OpenOffice free office suite, ver 3.4+ The GIMP ~ free photoshop Firefox web browser FlashBlock like it says!

SML:
 :: cons [x1,...] list [ ] list @ append fn => &lambda . : has type
Compared

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 21-Oct-2016 22:15:53 EST.