Session 23: Lazy evaluation

Lazy evaluation

Sections 3.3 and 3.4 from Hudak, Peterson, and Fasel's A Gentle Introduction to Haskell 98 give some examples of lazy evaluation. Here are the specific examples covered in class.

-- Non-strict functions (Sec 3.3)

infiniteRecur 0 = infiniteRecur 0

cond True thenValue elseValue = thenValue
cond False thenValue elseValue = elseValue

test = cond (1 + 1 == 2) "ok" (infiniteRecur 0)

-- Infinite data structures (Sec 3.4)

one = 1 : ones

powersOf2 = 1 : map ((*) 2) powersOf2

primesFrom n = if isPrime n then n : primesFrom (n + 1)
                            else primesFrom (n + 1)
primes = primesFrom 2

Supporting lazy evaluation

(Not in textbook) Consider the following definitions in Haskell, which defines the pow2 function which given n returns the nth power of 2.

double n = n + n

pow2 1 = 2
pow2 n = double (pow2 (n - 1))

You might naively think that the interpreter goes through the following steps to evaluate pow2 3.

pow2 3 = double (pow2 (3 - 1))
       = double (pow2 2)
       = double (double (pow2 (2 - 1)))
       = double (double (pow2 1))
       = double (double 2)
       = double (2 + 2)
       = double 4
       = 4 + 4
	   = 8

Note how this evaluates the argument to double before it calls the double function - that's eager evaluation, not lazy evaluation.

Lazy evaluation involves passing the argument to a function unevaluated. Thus, the following is more accurate.

pow2 3 = double (pow2 (3 - 1))
       = pow2 (3 - 1) + pow2 (3 - 1)
       = pow2 2 + pow2 (3 - 1)
       = double (pow2 (2 - 1)) + pow2 (3 - 1)
       = (pow2 (2 - 1) + pow2 (2 - 1)) + pow2 (3 - 1)
       = (pow2 1 + pow2 (2 - 1)) + pow2 (3 - 1)
       = (2 + pow2 (2 - 1)) + pow2 (3 - 1)
       = (2 + pow2 1) + pow2 (3 - 1)
       = (2 + 2) + pow2 (3 - 1)
       = 4 + pow2 (3 - 1)
       = 4 + pow2 2
       = 4 + double (pow2 (2 - 1))
       = 4 + (pow2 (2 - 1) + pow2 (2 - 1))
       = 4 + (pow2 1 + pow2 (2 - 1))
       = 4 + (2 + pow2 (2 - 1))
       = 4 + (2 + pow2 1)
       = 4 + (2 + 2)
       = 4 + 4
	   = 8

This evaluation is more accurate with how Haskell would evaluate it than the above. Notice how it's much slower, requiring the evaluation of pow2 (3 - 1) twice, and pow2 (2 - 1) twice for each of those. This function displays exponential behavior, whereas the eager evaluation technique does not.

But this isn't exactly what Haskell does either. Haskell creates a thunk to represent unevaluated expressions. Once a thunk's value is computed, then Haskell replaces it with the computed value. This way, each argument's value will be computed only once, or perhaps not at all. (With eager evaluation, each argument's value is computed exactly once.) Thus, the following is the most accurate diagram of the translation process working.

pow2 3 = double (pow2 (3 - 1))
       = pow2 (3 - 1) + pow2 (3 - 1)
       = pow2 2 + pow2 (3 - 1)
       = double (pow2 (2 - 1)) + pow2 (3 - 1)
       = (pow2 (2 - 1) + pow2 (2 - 1)) + pow2 (3 - 1)
       = (pow2 1 + pow2 (2 - 1)) + pow2 (3 - 1)
       = (2 + 2) + pow2 (3 - 1)
       = 4 + 4
	   = 8

In this derivation, the second pow2 (3 - 1) changes immediately when the computer has finished computing the value of the first pow2 (3 - 1), since this thunk refers to the same thunk as the one just computed to be 4.

Note that this won't work if we define double as follows.

pow2 1 = 2
pow2 n = pow2 (n - 1) + pow2 (n - 1)

This generates two different pow2 (n - 1) thunks, and so each thunk would have to be computed separately. The earlier example worked differently because only one pow2 (n - 1) thunk was created and passed into the double function.