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.

datatypeseq = consofint * (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.

funhead (cons (h, _)) = h;funtail (cons (_, t)) = force t;

These functions have types seq -> int and seq -> seq respectively.

**Exercise**

Write a function to give a list of the firstnintegers in a sequence.

We can construct a simple function which returns the infinite sequence which has the number one in every place.

funones () = 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.

funlcons (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.

funoneszeroes () = 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.

funfrom 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.

valnats = 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.

funtentimes (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).