Laziness and Strictness

Lazy Evaluation

Haskell expressions are evaluated by reducing them to the simplest possible form. 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 strategies to evaluate it: 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. 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

The two ways the expression three infinity could be evaluated are:

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 non-negative 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 useful because it returns a value:

> 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 101-st element on [0..]:

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

Since Haskell does not evaluate expressions until they’re needed, only the first 100 elements of [0..] are generated. In practice, infinite lists can be seen as a way of de-coupling loops from their stopping condition.

As another 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 error. So you should never evaluate undefined in a correct program.

Notice the difference between these two expressions:

> length [undefined,undefined]
2

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

The first expression 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 three:

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.