How lazy evaluation works in Haskell (by example)

This blog post is an answer to a question asked by Pat Shaughnessy in his excellent talk about Functional Programming and Ruby. His question circa at 24:00 in the video was about how Haskell internally implements lazy evaluation. I will answer this question by explaining what internally happens, when one evaluates the expression take 3 [5..] in Haskell. To avoid confusion with the integer numbers I changed the numbers compared to the example in the talk a bit.

First of all we need to clear up what [x..] really means. Due to the documentation of typeclass Enum the term [x..] is just syntactic sugoar for enumFrom x, which is defined as follows:

> enumFrom :: Int -> [Int]
> enumFrom x = x : enumFrom (x+1)

In Haskell we reason about computation as starting with a term and applying function definitions, until we reach a term we cannot simplify anymore. The process of simplifying the term is called reduction, whereas every single step is a reduction step, which I denote with the symbol =>.

Let us try to reduce the term enumFrom 5 by applying the function definition of enumFrom:

   enumFrom 5
=> 5 : enumFrom 6
=> 5 : 6 : enumFrom 7
=> 5 : 6 : 7 : enumFrom 8
=> ...

Obviously the reduction of enumFrom 5 will not terminate. So why does take 3 (enumFrom 5) terminate? Since reduction is about applying function definitions we need to take the definition of take into account:

> take :: Int -> [a] -> [a]
> take 0 _      = []
> take n []     = []
> take n (x:xs) = x : take (n-1) xs

The function take is defined by three equations, which handle different cases of parameter values and structure.

Now let us reduce the term take 3 (enumFrom 5). In an eager language we are evaluating the function arguments before applying the function definition, that is why eager evaluation is also called innermost evaluation. Considering Haskell to be eager our reduction would look like this:

   take 3 (enumFrom 5)
=> take 3 (5 : enumFrom 6)
=> take 3 (5 : 6 : enumFrom 7)
=> take 3 (5 : 6 : 7: enumFrom 8)
=> ...

Since the reduction of enumFrom 5 diverges, the reduction of take 3 (enumFrom 5) using innermost evaluation will not terminate. So there must be a neat trick preventing Haskell to run into that infinite loop. The trick is that Haskell is a lazy language, which means it always applies the outermost reduction.

What is the outermost reduction step we can apply in the term take 3 (enumFrom 5)? We can apply the function definition of take. So, let us try to find the right pattern to match in our function definition of take. In order to to this we are trying to match each equation of the definition with the given parameters in the function call. Since we handed in the paramter 3 the first equation will not match. What is the difference between equation two and three? In equation two the list is empty whereas in equation three it is not. Thus to decide which equation of take to apply, we need to find out whether the argument list (here: enumFrom 5) is empty or not. So we take a look at it:

   enumFrom 5
=> 5 : enumFrom 6

Recall that we are just looking whether the list is empty or not, we are not trying to compute the whole resulting list.

We just discovered that our argument list is build of a value 5 and a rest list enumFrom 6. This leads us to the fact to apply the third equation of take, since the argument list is not empty. We have to match the pattern take n (x:xs) to our term take 3 (enumFrom 5). The n matches 3, x matches 5 whereas xs matches enumFrom 1. Our equation says that take n (x:xs) will be reduced to x : take (n-1) xs, thus:

   take 3 (enumFrom 5)
=> 5 : take 2 (enumFrom 6)

This yields to the following reduction of take 3 (enumFrom 5), since the definition of take is always the outermost reduction to apply:

   take 3 (enumFrom 5)
=> 5 : take 2 (enumFrom 6)
=> 5 : 6 : take 1 (enumFrom 7)
=> 5 : 6 : 7 : take 0 (enumFrom 8)

We now reached a point, when applying the definition of take terminates our reduction, because take 0 of any list reduces to the empty list []. Thus the last reduction step is:

   5 :6 : 7 : take 0 (enumFrom 8)
=> 5 : 6 : 7 : []

Note that the term 5:6:7:[] is just the list [5,6,7]. This yields us to the whole reduction of take 3 [5..]:

   take 3 (enumFrom 5)
=> 5 : take 2 (enumFrom 6)
=> 5 : 6 : take 1 (enumFrom 7)
=> 5 : 6 : 7 : take 0 (enumFrom 8)
=> 5 : 6 : 7 : []

It turned out that Haskell can cope with infinite lists by default, because of the outermost (or lazy) evaluation. Hopefully this post cleared up things a bit. Do not hesitate to comment.

Advertisements

4 thoughts on “How lazy evaluation works in Haskell (by example)

  1. Awesome post! Definitely clears some things up for me. When pattern matching on the 0 case in take it might be helpful to take into account negatives. So, take n _ | n <= 0 = []. But for pedagogy doesn't seem too necessary.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s