Call by Need

Haskell’s evaluation strategy is called Call by Need or lazy evaluation. It is quite similar to Call by Name in that it only evaluates work that is needed for the result of the computation. At the same time, it avoids the main problem of Call by Name: it does not duplicate any work.

Sharing

The way in which lazy evaluation avoids duplication is known as sharing, or sometimes also as memoization. Instead of duplicating work, the work is shared, and when the work is performed once, all who share it can use the work’s results without redoing them.

Conceptually, we model sharing the work by using let binding:

  (\x -> x + x) (sin 1.0)
↣ let w = sin 1.0
   in w + w

To evaluate the sum in the body of the let binding, we first have to evaluate its left operand. As this operand is a let bound variable w, we consult the binding. The binding shows that the variable is bound to a reducible expression. Hence, we reduce...