The term “lazy evaluation” stems from the notion of deferring the computation of an expression to the point when it’s actually needed. Haskell, for example, supports lazy evaluation natively, in contrast to languages that evaluate expressions instantly. This is called “eager evaluation”, and it is the default for most programming languages, including functional programming languages like Lisp and Erlang.

Lazy evaluation is usually implemented by encapsuling the expression in a parameterless anonymous function, called a thunk. For example, let’s take a function when_null(A, B, C) that returns B if A equals the null atom, otherwise C. Like in an if statement we want B only be evaluated when A equals null otherwise we want to get C. A first draft in Erlang:

when_null(null, B, _) -> B;
when_null(_, _, C) -> C.

Now we call this function with the following arguments:

NewSalary = when_null(get_id(User),
    log:error("User not found: ", User), % log:error returns ok
    increase_salary(User, 100))

Obviously this is not what we intended, since both log:error and increase_salary are executed before stepping into when_null. The result in NewSalary is correct, after all, but with the side effect of executing log:error.

This is where Erlang’s Funs come into play. We can use them to model thunks explicitly:

when_null(null, B, _) -> B(); 
when_null(_, _, C) -> C().

when_null now excepts to be B and C to be Funs with arity 0. We then call when_null by wrapping the arguments in Funs:

NewSalary = when_null(get_id(User),
    fun() -> log:error("User not found", User) end,
    fun() -> increase_salary(User, 100) end)

This looks better now. The evaluation of the arguments is deferred and depending on the value of A only one of the arguments will be executed. All well, you might say, but a simple case statement would have just done it. That’s true, but with lazy evaluation you are able to model data structures that would be hard to implement otherwise. Note that we have to implement lazy evaluation explicitly in Erlang, so compared to Haskell the code is more verbose, since we have to wrap the lazy part in Funs.

Streams

One nice example for lazy data structures are streams. You can imagine streams as infinite lists, where the elements are evaluated lazily. Only the first element, called head, is present, the rest of the stream is represented by a Fun that describes how the following elements are computed. Abelson et al (see [1]) give a well written introduction to streams and implement them in Scheme. There are three fundamental operations: Construction (cons), getting the first element (head) and advancing the stream by one element (next). They must fulfill these properties:

head(cons(<a>, <b>)) = <a>
next(cons(<a>, <b>)) = <b>

Where <a> is some kind of value and <b> is a new stream. The implementation is straightforward:

cons(Head, NextStream) -> {Head, NextStream}.
head({Head, _}) -> Head.
next({_, NextStream}) -> NextStream().

Note that we introduced laziness by assuming that the tail of the stream is a parameterless Fun. That means we have to call cons always like this cons(<...>, fun() -> <...> end), constructing the stream out of a head element and a Fun. When requesting the next stream, the Fun is evaluated and expected to return the new stream. The stream object is nothing more than a tuple of the current head and Fun that “unpacks” the next stream. You can imagine it like a packet; upon retrieving the next element, we unpack it and get the stream advanced by one element.

A useful stream is the set of all integers. It has the following properties:

1 = head(integers()),
2 = head(next(integers())),
3 = head(next(next(integers()))),
...

Accessing an individual element this way is somewhat verbose. It would be nice if we can get it directly:

% Returns nth element of stream, starting from 1.
nth(1, Stream) -> head(Stream);
nth(N, Stream) -> nth(N - 1, next(Stream)).

% The above code get's a bit simpler:
1 = nth(1, integers()),
2 = nth(2, integers()),
3 = nth(3, integers()),
...

Before defining integers/0, let’s introduce some auxiliary functions to construct streams. advance/2 takes an initial start value and a Fun that calculates the next element from the previous one. This function makes it easy to create streams where each element depends on the previous one.

advance(Start, Next) ->
    cons(Start, fun() -> advance(Next(Start), Next) end).

Now we can define integers/0 right away:

integers() -> advance(1, fun(N) -> N + 1 end).

Filter and Map

We are used to operate on lists with functions like lists:filter and lists:map. We can define the same operations on streams, with the difference that they return a stream itself. Let’s look at the filter operation. Instead of going through all the elements of the stream and check if a certain predicate applies (which would be an impractical operation for mortal humans), we create a new stream that returns only the filtered elements.

OddIntegers = filter(fun(X) -> X rem 2 == 1 end, integers()),

1 = nth(1, OddIntegers),
3 = nth(2, OddIntegers),
5 = nth(3, OddIntegers),
...

Likewise works map. It returns a new stream with the mapped values.

SquaredOddIntegers = map(fun(X) -> X * X end, OddIntegers),

1 = nth(1, SquaredOddIntegers),
9 = nth(2, SquaredOddIntegers),
25 = nth(3, SquaredOddIntegers),
...

This is how filter/2 and map/2 are implemented:

% Returns a new stream with filtered values.
filter(Pred, Stream) ->
    case Pred(head(Stream)) of
         true ->
              cons(head(Stream), fun() -> filter(Pred, next(Stream)) end);
         false ->
              filter(Pred, next(Stream))
    end.

filter/2 takes a predicate Pred, which is a Fun with arity 1 that returns true or false for a given stream element and a stream as the second argument. In case of true it returns a new stream with the current head and wraps the tail in the filter. Otherwise it continues filtering the stream until it finds a head element that is accepted by the predicate.

		
% Returns a new stream with mapped values.
map(MapFun, Stream) ->
    cons(MapFun(head(Stream)), fun() -> map(MapFun, next(Stream)) end).

map/2 works similar; it takes a Fun/1 as first argument, which maps a given stream element to a new value and a stream and constructs a new stream with the mapped head element and wraps the tail in the MapFun.

We can use map to define another way of constructing streams, by calculating the value of an element from it’s position:

		
sequence(Fun) -> sequence(1, Fun).
sequence(Start, Fun) ->
    cons(Fun(Start), fun() -> map(Fun, integers(Start + 1)) end).

The sequence of the powers of 2, for example, is defined this way.

powers_of_2() -> sequence(1, fun(N) -> round(math:pow(2, N)) end).

% Example
2 = nth(1, powers_of_2()),
4 = nth(2, powers_of_2()),
128 = nth(7, powers_of_2())
...

Instead of using filter and map we could define SquaredOddIntegers directly by using sequence:

squared_odd_integers() ->
    sequence(1, fun (N) -> K = (2*N-1), K*K end).

Reduce

Let’s look at the reduce operation. It accumulates N elements of the stream, and returns a scalar. This is done by a Fun that takes the i. element and the accumulator and returns a new accumulator.

% Reduces N elements of a stream to a single value by applying
% ReduceFun to the first N elements.
%
% ReduceFun :: fun(Value, Acc0) -> Acc1
reduce(0, _, Result, _) -> Result;
reduce(N, ReduceFun, Acc0, Stream) ->
    reduce(N-1, ReduceFun, ReduceFun(head(Stream), Acc0), next(Stream)).

A stream-inspired implementation of the factorial exploits this function:

factorial(N) ->
    reduce(N, fun(V, Fac) -> V * Fac end, 1, integers()).

% Examples
6 = factorial(3),
24 = factorial(4),
120 = factorial(5)

No blog post on functional programming languages without Fibonacci numbers. I’m presenting the approach from Abelson et al [1, p. 329], since it’s a very clever recursive solution and worth to think about. The idea is to define the stream of Fibonacci numbers by adding a shifted version of the stream to itself. We state that the stream begins with 0 and 1 and then every successive Fibonacci number is the sum of two previous elements of the same stream. To do this elegantly we need an auxiliary function that creates a new stream by adding two streams element-wise:

% Returns a new stream where each elements are the sum of the
% corresponding values of Stream1 and Stream2.
add_streams(Stream1, Stream2) ->
    cons(head(Stream1) + head(Stream2),
        fun() -> add_streams(next(Stream1), next(Stream2)) end).

The Fibonacci numbers are defined by adding the stream of Fibonacci numbers to the tail of itself:

fibs() ->
    cons(0,                        % First element is 0
        fun() -> cons(1,           % Second element is 1
            fun() -> add_streams(  % Recursion kicks in
                next(fibs()),
                fibs()
            ) end)
        end).

If this makes your mind spin, a visual explanation may help (again, of Abelson et al fame):

           1   1   2   3   5   8  13  next(fibs)
           0   1   1   2   3   5   8  fibs()
   --------------------------------------------
   0   1   1   2   3   5   8  13  21  fibs()

The main idea of streams in the context in pure functional programming languages is to introduce a notion of time and state. We advance in “stream-time” by calling next, which, in all of our cases, changes the state of the stream by calculating a new head element. Note that with this approach the time of a stream is decoupled from the real-time. As a variable changes its state over time in the imperative paradigm, so does the stream when we advance through its elements.

Reversable streams

We can push streams even further by introducing reversable streams, which allow us to go back in time. We can achive this by simply adding another Fun that computes the previous stream:

cons(A, B, C) -> {A, B, C}.
head({A, _, _}) -> A.
next({_, B, _}) -> B().
prev({_, _, C}) -> C(). % Calcs the previous stream 

To “undo” a next operation, we call prev. This executes the third element of the tuple, which is expected to return the predecessor of the current stream. Our functions to create new streams need just a little rewrite to support reversable streams:

% Next :: Fun(a_i) -> a_{i+1}
% Prev :: Fun(a_i) -> a_{i-1}
advance(Start, Next, Prev) ->
    cons(Start, 
        fun() -> advance(Next(Start), Next, Prev) end,
        fun() -> advance(Prev(Start), Next, Prev) end).

sequence(Start, Fun) ->
    cons(Fun(Start),
        fun() -> sequence(Start + 1, Fun) end,
        fun() -> sequence(Start - 1, Fun) end).

Note that advance now needs two Funs, Next and Prev: Next returns the successor of a given element, while Prev returns the predecessor. The interface of sequence stays the same, since we can compute each element of the stream from it’s position directly. Hence, the reversable stream of integers looks like this:

integers() ->
    sequence(1, fun(M) -> M end).

Our function to access the Nth element needs a modification. The parameter N is always relative to the current stream, so nth(M + 1, stream) == nth(M, next(stream)) and nth(M - 1, stream) == nth(M, prev(stream)).

% Returns nth element of stream.
nth(1, Stream) -> head(Stream);
nth(N, Stream) when N < 1 -> nth(N + 1, prev(Stream));
nth(N, Stream) -> nth(N - 1, next(Stream)).

% Example
-4 = nth(-4, integers())
-3 = nth(-4, next(integers())

Likewise, implementing map is straightforward:

map(Fun, Stream) ->
    cons(Fun(head(Stream)),
       fun() -> map(Fun, next(Stream)) end,
       fun() -> map(Fun, prev(Stream)) end).

Implementing filter needs some clarification about moving forward and backward. Our current implementation of filter moves the stream silently forward until it’s head matches the predicate. This means filter itself implicitly contains a move operation we have to make explicit when dealing with reversable stream. Thus we have to create two filter functions, one that moves the stream forward on a non-matching head and one that moves it backwards.

% Helper function. Constructs a filtered stream.
% Invariant: Pred(head(Stream)) == true.
filter_cons(Pred, Stream) ->
    cons(head(Stream),
        fun() -> filter_next(Pred, next(Stream)) end,
        fun() -> filter_prev(Pred, prev(Stream)) end).
	
filter_next(Pred, Stream) ->
     case Pred(head(Stream)) of
         true -> filter_cons(Pred, Stream);
         false -> filter_next(Pred, next(Stream))
     end.

filter_prev(Pred, Stream) ->
     case Pred(head(Stream)) of
         true -> filter_cons(Pred, Stream);
         false -> filter_prev(Pred, prev(Stream)) 
     end. 

% filter moves forward by default.
filter(Pred, Stream) -> filter_next(Pred, Stream).

When we call prev on a filtered stream, filter_prev is executed recursively until a head element matches the predicate. Likewise works next, just in the opposite direction.

An example: digital signals

With this toolset we can model digital signals. Erlang is definitly not the language of choice for doing DSP stuff, but the conceptual similarity between digital signals and streams is too alluring. Imagine a sine wave that goes on infinitely with a certain frequency:

sine(Time, Frequency) -> math:sin(2*math:pi()*Frequency*Time).

The parameter Time is a continuous value, ranging from -∞ to +∞. We want to work with different signals, where each signal is a function depending only on time. The standard pitch A is such a signal.

sine_440Hz(Time) -> sine(Time, 440).
sine_1Hz(Time) -> sine(Time, 1).

To make signals compatible with streams we have to transfrom the continuous parameter Time to a discrete one by sampling the signal with a certain frequency.

sampled_signal(Signal, SampleFrequency) ->
    sequence(0, fun(N) -> Signal(1.0/SampleFrequency * N) end).

By using sampled_signal we transform a continuous-time signal to a discrete stream, where each call to head returns the current sample and we are free to move back and forth on the sampled signal with next and prev. Lets look at some values:

% Sampling a 1Hz sine with 10Hz sample frequency.
SampledSignal = sampled_signal(fun sine_1Hz/1, 10) 

0 = nth(1, SampledSignal)
0.951 = round(nth(3, SampledSignal)*1000)/1000
0.587 = round(nth(5, SampledSignal)*1000)/1000
-0.587 = round(nth(7, SampledSignal)*1000)/1000
-0.951 = round(nth(9, SampledSignal)*1000)/1000
0 = nth(11, SampledSignal)

Which is what we expected:

References

1. Abelson, H.; Sussman, G.; Sussman, J. (1996): Structure and Interpretation of Computer Programs. Cambridge, Mass.: MIT Press.