What laziness is not

In programming, laziness is a strategy which delays the evaluation of an expression until its value is needed. Using Haskell, you might have encountered lazy evaluation in expressions like:

take 10 [1,3..]

where [1,3..] is the infinite list of odd numbers (1,3,5,7,…). Haskell manages to return the correct result [1,3,5,7,9,11,13,15,17,19] because it does not compute the whole odd-numbers-list, but just the elements needed to give an answer (in this case, the first ten numbers of the list). A similar example in eager languages (C, Scheme, etc.), would hang forever trying to reach the bottom of [1,3..].

Lazy evaluation is a powerful tool in the hands of a programmer, but can leave Haskell newcomers boggled (“Will this expression be evaluated?”, “Is this going to loop forever?”, “Why isn’t this lazy?”). Test your knowledge with this simple exercise:

-- Will this expression return something?
foldr1 (||) (repeat True)

-- What about this one?
foldl1 (||) (repeat True)

Check your answers using GHCi; if you made any mistakes or were unsure about the behaviour of those functions, read on.

An unambiguous definition of laziness

In a section of the Gentle Introduction to Haskell, which deals with pattern matching, we can read:

The [pattern] matching process itself occurs “top-down, left-to-right.”

This is everything you are going to need to consider laziness of functions. As an example, check this expression:

(1 == 1) || undefined
-- undefined stops execution and outputs an error

Will this function return something or crash? The temptation is to reason along the lines of:

Well, this is a simple Boolean operator in which, if one of the two parameters is True, the return value will be True Since (1==1) is True the condition is satisfied and the expression will evaluate to True

But that would be wrong! To be able to correctly answer this question, we need to examine the way the function performs pattern matching, nothing more, nothing less. Let us examine the source from the Prelude:

-- | Boolean \"or\"
(||)          :: Bool -> Bool -> Bool
True  || _    =  True
False || x    =  x

Knowing that, the compiler/interpreter will (in a top-to-bottom left-to-right fashion), execute this steps:

Now that we know how to (verbosely) reason as a compiler, let us take a look at a similar function:

-- my implementation of Boolean "or"
myOr            :: Bool -> Bool -> Bool
myOr False x    =  x
myOr _     True =  True
myOr True  _    =  True

This implementation of or is slightly naive but the results will be equivalent to the one provided by the Prelude, i.e.:

myOr True  True  = True  || True
myOr True  False = True  || False
myOr False True  = False || True
myOr False False = False || False

Knowing that, what will:

myOr (1==1) undefined

evaluate to? Remember, the rule is simple, top to bottom, left to right:

It is easy to write different implementations with different evaluating behaviours. As the patterns matched change, so will the function laziness.

More complex cases

You do not have to “play the compiler” every time you consider laziness; make sure to familiarise with common higher order functions, though. Let us get back to the initial question:

-- Will this expression return something?
foldr1 (||) (repeat True)

-- What about this one?
foldl1 (||) (repeat True)

The list is infinite, but we know that applying or to a single True value will suffice. Take a look at foldr1 and foldl1 implementations:

foldr1                  :: (a -> a -> a) -> [a] -> a
foldr1 _ [x]            =  x
foldr1 f (x:xs)         =  f x (foldr1 f xs)
foldr1 _ []             =  errorEmptyList "foldr1"

foldl1                  :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs)         =  foldl f x xs
foldl1 _ []             =  errorEmptyList "foldl1"

Since we are dealing with infinite lists, the singleton pattern [x] (a list of a lone element) or the empty list [] will never be matched. We can then rewrite these functions as:

foldr1                  :: (a -> a -> a) -> [a] -> a
foldr1 f (x:xs)         =  f x (foldr1 f xs)

foldl1                  :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs)         =  foldl f x xs

We see that foldr1 immediately calls f x ...; the second element (foldr1 f xs) would need an infinite recursion to be calculated, but we do not need it.

On the other hand, foldl1 calls another higher order function foldl ... (which in turn calls another higher order function, and so on); f never gets a chance to pattern match its first parameter. That is why foldr1 “escapes” infinite recursion and return True while foldl1 hangs.


I hope the examples helped you understanding what laziness is and is not. Lessons to be learned: