Laziness and Strictness

Lazy Evaluation

Haskell expressions are evaluated by reducing them to the simplest possible form and printing the result. For example, suppose we have this function that squares numbers:

sqr :: Integer -> Integer
sqr n = n * n

Consider the expression sqr(3+4). There are two main ways that it can be evaluated: either 3+4 is evaluated first (known as eager evaluation, or the sqr function is evaluated first (known as lazy evaluation).

Here is how eager evaluation works, i.e. when 3+4 is evaluated first:

sqr(3 + 4)    -- eager evaluation (innermost reduction)
= sqr 7
= let n=7 in n*n
= 7*7
= 49

Here is lazy evaluation where 3+4 is not evaluated until it is needed inside of sqr:

sqr(3+4)      -- lazy evaluation (outermost reduction)
= let n=3+4 in n*n
= let n=7 in n*n
= 7*7
= 49

Sometimes the reduction strategy can make a big difference in how an expression is evaluated. For example, consider the fst function: it returns the first element of a pair, i.e. fst (x,y) = x:

fst (sqr 1, sqr 2)   -- eager evaluation (innermost reduction)
= fst (1*1, sqr 2)
= fst (1, sqr 2)
= fst (1, 2*2)
= fst (1, 4)
= 1

fst (sqr 1, sqr 2)   -- lazy evaluation (outermost reduction)
= let p = (sqr 1, sqr 2) in fst p
= sqr 1
= 1 * 1
= 1

In the lazy evaluation, sqr 2 is not evaluated.

Here’s another example:

infinity :: Integer
infinity = 1 + infinity

three :: Integer -> Integer
three x = 3

Consider the two ways the expression three infinity could be evaluated:

three infinity   -- eager evaluation (innermost reduction)
= three (1 + infinity)
= three (1 + (1 + infinity))
= three (1 + (1 + (1 + infinity)))
= ...
-- never ends!

three infinity   -- lazy evaluation (outermost reduction)
= let x = infinity in 3
= 3

So the expression three infinity cannot be evaluated correctly using eager evaluation.

Haskell uses lazy evaluation for all functions. On the plus side, lazy evaluation never does more reduction steps than eager evaluation, and sometimes many fewer. On the minus side, lazy evaluation can use a lot more memory in some cases, and it can be difficult to predict its performance ahead of time.

Infinite Lists

Thanks to its use of lazy evaluation, Haskell can sometimes do useful calculations with infinite lists. The trick is to ensure that you never evaluate the entire list, since that will result in an infinite loop.

For example, [0..] is the infinite list [0,1,2,3,4,...], i.e. all positive integers. If you try to evaluate this in the interpreter you get this:

> [0..]
[0,1,2,3,4,5,6,7,8,9,10,11 ...
-- prints forever!

But this expression is more useful:

> take 5 [0..]
[0,1,2,3,4]

The standard take n lst function returns the first n` items of ``lst. Items n+1 onwards are not needed and so are not evaluated by take.

Similarly, this expression evaluates to the 101st element on [0..]:

> head (drop 100 [0..])
100

Practically, speaking, you think of [0..] like a loop that calculates the values starting at 0, and and incrementing 1 at a time. No stopping condition for the loop is given. But since it is not actually evaluated until it is need, and even then only one iteration at a time is done, in some cases (like the two shown above) it can do useful work.

In practice, infinite lists can be seen as a way of de-coupling loops from their stopping condition. For example, the function repeat x returns an infinite list containing just copies of x, e.g.:

> repeat 4
[4,4,4,4,4,4,...]

Combining this with the take function gives an easy way to create a list containing n copies of some value, e.g.:

> take 5 (repeat 4)
[4,4,4,4,4]

> take 3 (repeat '.')
"..."

The standard Haskell function replicate n x does exactly this, and so that’s probably easier to use in real programs. Nonetheless, it is instructive to see how infinite lists and lazy evaluation can work together in a useful way.

Undefined Values

Sometimes when you evaluate a Haskell expression you get an error, e.g.:

> 1 `div` 0
*** Exception: divide by zero

Mathematically speaking, we can say that 1 `div` 0 has the special value undefined. In mathematics, undefined is sometimes called bottom.

Practically speaking, you can think of undefined as a special value that, when evaluated, always causes an an error. So you should never evaluate undefined in a correct program. It doesn’t show up very often in practical programs, but it is useful for discussing some important properties of Haskell.

Notice the difference between these two expressions:

> length [undefined,undefined]
2

> head [undefined,undefined]
*** Exception: Prelude.undefined

The first expressions correctly returns the length of the list, even though all the values on it are undefined. The length function does not evaluate any elements on the list it is calculating the length.

In contrast, head [undefined,undefined] is an error because it extracts the first element of the list and then evaluates it.

Strictness

A Haskell function f is said to be strict if f undefined = undefined. Otherwise, the function is said to be non-strict. Lazy evaluation lets Haskell define non-strict functions, such as the three function:

three :: Integer -> Integer   -- a non-strict function
three x = 3

For example:

> three x = 3
> three undefined
3

Since Haskell allows non-strict functions to be defined, it is called a non-strict language.

Most mainstream languages are strict, i.e. in a strict language passing an undefined value to a function always results in undefined output.