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.

Fascinating! Conceptually I knew lazy evaluation must work this way, but it’s great to see how you worked through this example and explained it so well. Thanks!

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.

As far as I know, you just explained the operational semantics of call-by-name. Lazy evaluation works operationally like call-by-need, but uses sharing, thus an expression is not evaluated twice. In the end, lazy evaluation is a “better” version of call-by-name (http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need).

Yep, you are right. Probably the title is a bit too catchy.