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:

• Take the topmost pattern, True _. Can I pattern match against it? The answer is: “if and only if the single patterns composing it, True and _, both match”.
• Having to examine two patterns, proceed from the left: True. Does it match? To check this I need to calculate the value of (1==1), which is True; great, it does match!
• The second pattern is marked as _, which means “match always”. There have not been matching errors and the line is over, hence the whole pattern is correctly matched; do what it is written on the right side of = (i.e. return True).

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:

• Take the topmost pattern myOr False x. Will this match? The first parameter from the left should be False. To check it against my expression I need to evaluate (1==1). Mhh, I was expecting a False and I got a True, this will not do it.

• Next pattern is the one right below the first: myOr _ True. Again from left to right: the underscore means “it will always match”, so I will not even bother to calculate the value of (1==1). Second parameter should be True, though; I need to calculate the result of the expression undefined to match against this.

  Evaluating undefined will cause our program to exit with a run-time error.

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.

Conclusions

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

• Laziness is not magical nor complex; at its core it has to do with pattern matching and with the fact that Haskell matches patterns top to bottom, left to right.
• The compiler knows nothing about the problem at hand. Any theorem, logical deduction, etc. that you the pregrammer might be aware of will be ignored. The only things that matter are patterns.
• The compiler will not reorder the way pattern matches are written. If you have in mind a function which must be lazy in certain situations, make sure it is written according to the behaviour you expect.
• Higher order functions, especially on lists, are the bread and butter of functional programming. It is wise to spend some time learning and studying them, so predicting lazy/strict behaviour will become natural while coding.