Although any call-by-value function can be transformed into a call-by-name variant the chief interest in delaying evaluation in functional programming is the ability to create datatypes such as infinite sequences and infinitely branching trees. In a shocking and inexcusable abuse of technical terminology we will call these `lazy' datatypes even though they simulate call-by-name evaluation instead of call-by-need evalution. The most important point about these datatypes is the representation ability which they offer; not that they optimise computations.
Consider the datatype of infinite sequences of integers. This can be described as a Standard ML datatype with a single constructor, cons.
datatype seq = cons of int * (seq delayed);
This definition provides us with a constructor, cons, of type (int * (seq delayed)) -> seq. The functions to return the head and tail of an infinite sequence are much simpler than those to return the head and tail of a list. Since the sequence can never be exhausted there is no exceptional case behaviour. However, note that the tail function is partial since the evaluation of force t may fail to terminate.
fun head (cons (h, _)) = h; fun tail (cons (_, t)) = force t;
These functions have types seq -> int and seq -> seq respectively.
Exercise
Write a function to give a list of the first n integers in a sequence.
We can construct a simple function which returns the infinite sequence which has the number one in every place.
fun ones () = cons (1, ones);
Unfortunately the cons constructor has the property that it does not compose since cons(first, cons(second, tail)) is not well-typed. Life is much easier if we define a lazy version of cons which does compose.
fun lcons (h, t) () = cons (h, t);
We may now easily define the infinite sequence which has one in first place and in every other odd place with every other digit being zero.
fun oneszeroes () = cons (1, lcons (0, oneszeroes));
In general we may define more interesting sequences by thinking of defining a whole family of sequences simultaneously. For example, the sequences which start at n and move up in steps of one.
fun from n () = cons (n, from (n + 1));
Using the from function we may define the sequence of all natural numbers quite easily. These are simply all the numbers from zero upwards.
val nats = force (from 0);
Given a sequence constructed in this way we could produce another infinite sequence by supplying a function which can be applied to each element of the sequence, thereby generating a new sequence. The function tentimes, when applied to a sequence s, will return a sequence where the elements are the corresponding elements of s multiplied by ten.
fun tentimes (cons(h, t)) = cons(10 * h, tentimes o t);
Using this function we may define tens as the result of the composition (tentimes o ones) and hundreds as the result of the composition (tentimes o tentimes o ones).