As we saw earlier, a `datatype`

declaration is
used to introduce a new type whose elements are generated by a given set of value
constructors. The value constructors may be used to create values of the type (by
applying them to values of suitable type), and to decompose values of the type (by using
them in patterns). Value constructors, like all other functions in ML, are evaluated
*eagerly*, meaning that the arguments to the constructor are evaluated before the
constructor is applied. For example, to attach an element to the front of a list, we
first determine the value of the element and the value of the list before building a new
list with that element as head and that list as tail. This policy is based on the
intuitively appealing idea of a list as a kind of value that we manipulate by using the
list constructors as functions and as patterns.

An alternative is to view a data structure as being perpetually in the process of
creation, rather than as a result of a completed computation. According to this view
a list may be thought of as a "partial", or "suspended", computation
that, when provoked, computes just far enough to determine whether the end of the list has
been reached, or , if not, to produce the next element of the list together with a
suspended computation to compute the remainder of the list. An added benefit of this
viewpoint is that it is then possible to define *infinite lists* (better known as *streams*)
that continually generate the next element, without ever reaching the end of the list.
This view of data structures as being in the process of creation conflicts with the
eager evaluation strategy just described since under the eager approach all expressions
are fully evaluated before they are used, whereas we would like to evaluate them only as
much as absolutely necessary to allow the overall computation to proceed. This is
called, appropriately enough, *lazy evaluation*.

Standard ML does not support lazy evaluation as a primitive notion; it can be
implemented "by hand" using methods that are described later in these notes.
However, Standard ML of New Jersey (from version 110.5) does provide for lazy
evaluation through an extension of the `datatype`

and `val rec`

declaration forms. We will illustrate these mechanisms by defining a type ```
'a
stream
```

of streams of values of type `'a`

. Based on the discussion
above you might imagine that a stream is just an infinite list, but it is important to
keep the two concepts separate. Lists are eager types whose values are generated by
finitely-many applications of `::`

to the empty list, `nil`

.
Streams are lazy types whose values are determined by suspended computations that generate
the next element of the stream (and another computation to generate the remainder).
The two concepts are, and ought to be kept separate since they serve different purposes
and require different modes of reasoning.

First off, the lazy evaluation mechanisms of SML/NJ must be enabled by evaluating the following declarations:

Compiler.Control.Lazy.enabled := true;

open Lazy;

We may then define a type of streams as follows:

datatype lazy 'a stream = Cons of 'a * 'a stream

The keyword "`lazy`

" indicates that values of type `'a stream`

are suspended computations that, when evaluated, yield a value of the form ```
Cons (x,
c)
```

, where `x`

is a value of type `'a`

, and `c`

is
another value of type `'a stream`

, *i.e.*, another computation of such a
value.

How might a value of type `'a stream`

be created? Since the
description of values of this type we've just given is clearly "circular", we
must employ a recursive value binding to create one. Here's a definition of the
infinite stream of `1`

's as a value of type `int stream`

:

val rec lazy ones = Cons (1, ones)

The keyword "`lazy`

" indicates that we are defining a value of a
lazy type, which means that it must be kept as an incomplete computation, rather than
fully evaluated at the time the binding is created. What computation is bound to `ones`

?
It's the computation that, when evaluated, yields `Cons (1, ones)`

, a
stream whose head element is `1`

and whose tail is the very same computation
again. Thus if we evaluate the tail of `ones`

we will, once again, obtain
the same value, and so on *ad infinitum*.

How can we take apart values of stream type? By pattern matching, of course! For example, we may evaluate the binding

val Cons (h, t) = ones

to extract the head and tail of the stream `ones`

. To perform the
pattern match we must first force the evaluation of `ones`

to obtain ```
Cons
(1, ones)
```

, then pattern match to bind `h`

to `1`

and `t`

to `ones`

. Had the pattern been "deeper", further evaluation
would be forced, as in the following binding:

val Cons (h, (Cons (h', t')) = ones

To evaluate this binding, we evaluate ones to `Cons (1, ones)`

, binding `h`

to `1`

in the process, then evaluate `ones`

again to ```
Cons (1,
ones)
```

, binding `h'`

to `1`

and `t'`

to `ones`

.
The general rule is *pattern matching forces evaluation of partial computations
up to the depth required by the pattern*.

We may define functions to extract the head and tail of a stream as follows:

fun shd (Cons (h, _)) = h

fun stl (Cons (_, s)) = s

Both of these functions force the computation of the stream when applied so that they
may extract the head and tail elements. In the case of the head element it is clear
that the stream computation *must* be forced in order to determine its value, but a
moment's thought reveals that it is *not* strictly necessary to force the
computation of a stream to extract it's tail! Why is that? Since the tail of a
stream is itself a stream, it may be thought of as a suspended computation. But
which suspended computation is it? According to the definition just given, it is the
suspended stream computation extracted from the second component of the value of the given
stream. But another definition is possible: it is the suspended computation that, *when
forced*, yields the second component of the result of forcing the stream computation.
Here's a definition:

fun lazy lstl (Cons (_, s)) = s

Here the keyword "`lazy`

" indicates that an application of `lstl`

to a stream does *not* immediately perform pattern matching (hence forcing the
argument), but rather merely *sets up* a delayed stream computation that, when
forced, forces the argument and extracts the tail of the stream.

The behavior of the two forms of tail function can be distinguished as follows:

val rec lazy s = (print "."; Cons (1, s));

val s' = stl s; (* prints "." *)

val Cons _ = s'; (* silent *)

val rec lazy s = (print "."; Cons (1, s));

val s'' = lstl s; (* silent *)

val Cons _ = s''; (* prints "." *)

Notice that since `stl`

immediately forces it's argument, the "`.`

"
is printed when it is applied, whereas it is printed only when the result of applying `lstl`

to an argument is itself forced by another pattern match.

It is *extremely important* that you understand the difference between these two
definitions! To check your understanding, let's define a function `smap`

that applies a function to every element of a stream, yielding another stream. The
type of `smap`

should be `('a -> 'b) -> 'a stream -> 'b stream`

.
The thing to keep in mind is that the application of `smap`

to a
function and a stream should set up (but not compute) another stream that, when forced,
forces the argument stream to obtain the head element, applies the given function to it,
and yields this as the head of the result. Here's the code:

fun smap f =

let

fun lazy loop (Cons (x, s)) = Cons (f x, loop s)

in

loop

end

Notice that we have "staged" the computation so that the partial application
of `smap`

to a function yields a function that loops over a given stream,
applying the given function to each element. This loop is a "lazy"
function to ensure that an application of loop to a stream merely sets up a stream
computation, rather than forcing the evaluation of its argument at the time that the loop
is applied. This ensures that we are as lazy as possible about evaluating streams.
Had we dropped the keyword "`lazy`

" from the definition of the
loop, then an application of `smap`

to a function and a stream would
immediately force the computation of the head element of the stream, rather than merely
set up a future computation of the same result. This would be a bit over-eager in
the case that the result of applying `smap`

were never used in a subsequent
computation. Which solution is "right"? It all depends on what
you're doing, but as a rule of thumb, it is best to be as lazy as possible when dealing
with lazy types.

To illustrate the use of smap, here's a definition of the infinite stream of natural numbers:

val one_plus = smap (fn n => n+1)

val rec lazy nats = Cons (0, one_plus nats)

It is worthwhile contemplating how and why this definition works.

Now let's define a function `sfilter`

of type ```
('a -> bool) -> 'a
stream -> 'a stream
```

that filters out all elements of a stream that do not
satisfy a given predicate. Here's the code:

fun sfilter pred =

let

fun lazy loop (Cons (x, s)) =

if pred x then Cons (x, loop s) else loop s

in

loop

end

We can use filter to define a function `sieve`

that, when applied to a
stream of numbers, retains only those numbers that are not divisible by a preceding number
in the stream:

fun m mod n = m - n * (m div n)

fun divides m n = n mod m = 0

fun lazy sieve (Cons (x, s)) = Cons (x, sfilter (not o (divides x)) s)

We may now define the infinite stream of primes by applying `sieve`

to the
natural numbers greater than or equal to 2:

val nats2 = stl (stl nats) (* might as well be eager *)

val primes = sieve nats2

To inspect the values of a stream it is often useful to use the following function that
"takes" *n>=0* elements from a stream and builds a list of those *n*
values:

fun take 0 _ = nil

| take n (Cons (x, s)) = x :: take (n-1) s

In addition to supporting demand-driven computation the lazy evaluation primitives of
SML/NJ also support *memoization* of the results of a computation. The idea
is that a delayed computation is performed *at most once*. If it is never
forced by pattern matching, then the delayed computation is never performed at all.
If it is ever forced, then the result of forcing that computation is stored in a memo pad
so that if it is forced again, the previous result is returned immediately,without
repeating the work that was done previously. Here's an example to illustrate the
effects of memoization:

val rec lazy s = Cons ((print "."; 1), s)

val Cons (h, _) = s; (* prints ".", binds h to 1 *)

val Cons (h, _) = s; (* silent, binds h to 1 *)

Replace "`print ".";1`

" by a time-consuming operation
yielding `1`

as result, and you will see that the second time we force `s`

the result is returned instantly, taking advantage of the effort expended on the
time-consuming operation induced by the first force of `s`

.