Laziness example from the Learn You a Haskell for Great Good book

Question

I'm reading the introduction of Learn You a Haskell for Great Good and I can't understand the following explanation of the term "lazy".

Say you have an immutable list of numbers xs = [1,2,3,4,5,6,7,8] and a function doubleMe which multiplies every element by 2 and then returns a new list. If we wanted to multiply our list by 8 in an imperative language and did doubleMe(doubleMe(doubleMe(xs))), it would probably pass through the list once and make a copy and then return it. Then it would pass through the list another two times and return the result. In a lazy language, calling doubleMe on a list without forcing it to show you the result ends up in the program sort of telling you "Yeah yeah, I'll do it later!". But once you want to see the result, the first doubleMe tells the second one it wants the result, now! The second one says that to the third one and the third one reluctantly gives back a doubled 1, which is a 2. The second one receives that and gives back 4 to the first one. The first one sees that and tells you the first element is 8. So it only does one pass through the list and only when you really need it.

What's the magic behind the doubleMe function? What are the differences between the imperative and the functional version?

Answer 1

The trouble with wrapping your head around laziness, if you're used to strict programming, is that laziness never changes the result when strict evaluation is able to produce a result.¹

So looking at examples you already understand and trying to see how lazy evaluation changes the picture, can be confusing because the answer is mostly "it doesn't". Lazy vs strict evaluation can sometimes make a big difference in performance characteristics (in either direction). More importantly, there is code that you can execute under lazy evaluation which will fail under strict evaluation.

So lazy evaluation basically doesn't change any of the code you already knew how to write, but enables you to write code that you couldn't with strict evaluation!

So print doubleMe(doubleMe(doubleMe([1, 2, 3, 4, 5]))) doesn't mean anything different under strict or lazy evaluation. We can talk details of how it's implemented and find out that the various doublings will take place in a different order, and maybe that's enough for some people to get the intuition. But I'm not sure it's the best way to introduce the concept.

Where laziness really starts looking different is that you can do things like:

1. Write a program to print the Nth prime number, by generating a list of all primes and then printing the Nth element of the list. With lazy evaluation, the primes are only generated as they're requested, so this doesn't run foever. A strict program would have to have an argument to the generate_primes function to control how many to generate.

2. Write a program to keep printing prime numbers forever (until control-C is hit), by mapping the print function over a list of all prime numbers. With lazy evaluation they'll be printed as they're generated; a strict program would try to generate all the prime numbers before it printed any of them. Note that the lazy program can use the same generate_primes function from (1), whereas the strict program's generate_n_primes function is useless here (unless we want to generate all the primes up to the Nth again each time we print the N + 1th prime).

3. A slightly less silly example would be to have a program that converts a document to HTML, PDF, Latex, and dozens of other formats, and returns them all in a big dictionary to allow the caller to pick which one it wanted. Under strict evaluation, that would do the work of producing all the representations, even if the caller only wants one. Under lazy evaluation, a caller can pick and choose any of the representations it wants and the program will only actually execute the conversions that are actually required.

4. Define your own control structures. In a lazy language, something equivalent to if/then/else can be defined in user code as an ordinary function. The function takes a boolean value (the condition), and a value to return if the bool is true and a value to return if the condition is false. Only the "then" or "else" value will be evaluated, so this works even if the reason you're testing is that the "then" branch will cause an error that kills the program if the condition is false! You can define other control-structure-like functions as well.

And so on.

The way this works is that whenever a function call is evaluated, rather than going away and doing all of the work and then returning a result, it instead returns immediately. It doesn't have the result yet, so it returns a placeholder that contains enough information to do the work if it's ever actually needed.

This placeholder can be passed to other functions, stored in data structures, etc, exactly as if it was the real result. If some code later needs to "make a decision" (what character to print to the screen, which branch to take in a conditional, that kind of thing) based on the result that should be where the placeholder is, the code is executed "a bit more" to come up with just enough actual data to make the decision.

---

¹ Unless the code involved has side effects, which is why imperative programming languages never have implicit lazy evaluation everywhere. At most they have manually declared laziness, which comes with the caveat that it's the programmer's responsibility to make sure that it doesn't matter when/whether the code they declare as lazy is run.

Answer 2

Well, let's illustrate it. First, here's a simple definition of doubleMe:

doubleMe [] = []
doubleMe (x:xs) = x*2 : doubleMe xs

Now, let's consider how a strict/eager language (not Haskell) evaluates doubleMe (doubleMe (doubleMe [1, 2, 3])). The rule in such a language is this: to evaluate a function call, evaluate all of the arguments completely, then pass them to the function. So we get this:

doubleMe (doubleMe (doubleMe [1, 2, 3]))

  -- Expand the list literal into its structure
  == doubleMe (doubleMe (doubleMe (1 : 2 : 3 : [])))

  -- Eager evaluation requires that we start at the innermost use of doubleMe
  -- and work there until we produce the whole list.
  == doubleMe (doubleMe (2 : doubleMe (2 : 3 : [])))
  == doubleMe (doubleMe (2 : 4 : doubleMe (3 : [])))
  == doubleMe (doubleMe (2 : 4 : 6 : doubleMe []))
  == doubleMe (doubleMe (2 : 4 : 6 : []))

  -- Only now we can move on to the middle use of doubleMe:
  == doubleMe (4 : doubleMe (4 : 6 : []))
  == doubleMe (4 : 8 : doubleMe (6 : []))
  == doubleMe (4 : 8 : 12 : doubleMe [])
  == doubleMe (4 : 8 : 12 : [])
  == 8 : doubleMe (8 : 12 : [])
  == 8 : 16 : doubleMe (12 : [])
  == 8 : 16 : 24 : doubleMe []
  == 8 : 16 : 24 : []
  == [8, 16, 24]

In Haskell, the rule is more like this (but not exactly so):

1. To evaluate a function application, you apply the function before you evaluate its arguments.
2. If the outer function has multiple cases (like our doubleMe definition does), then we evaluate only enough of its argument to figure out which case to use.

So we get something like:

doubleMe (doubleMe (doubleMe [1, 2, 3]))
  -- Here we only "pull out" the 1 from the list, because it's all we need to
  -- pick which case we want for doubleMe.
  == doubleMe (doubleMe (doubleMe (1 : [2, 3])))
  == doubleMe (doubleMe (1*2 : doubleMe [2, 3]))

  -- Now instead of continuing with the inner doubleMe, we move on immediately
  -- to the middle one:
  == doubleMe ((1*2)*2 : doubleMe (doubleMe [2, 3]))

  -- And now, since we know which case to use for the outer doubleMe, we expand 
  -- that one:
  == (1*2)*2)*2 : doubleMe (doubleMe (doubleMe [2, 3]))

And in Haskell, evaluation stops here unless there is another caller that demands the value of the head or tail of the list. (Note that I didn't even do the multiplications.) For example, head is the function that returns the first element of a list:

head (x:xs) = x

Suppose we were evaluating head (doubleMe (doubleMe (doubleMe [1, 2, 3]))). This is how it would go:

head (doubleMe (doubleMe (doubleMe [1, 2, 3])))
  -- repeat the steps from above for the doubleMe part
  head (((1*2)*2)*2 : doubleMe (doubleMe (doubleMe [2, 3]))

  -- By the definition of head:
  ((1*2)*2)*2

So the doubleMe (doubleMe (doubleMe [2, 3])) part is discarded in this case, because head doesn't need it to produce a result. If Haskell wasn't lazy, it'd compute the whole [8, 12, 24] list and then take the 8 off the front.

GHC is even smarter than this. We can use the map function to write doubleMe:

doubleMe = map (*2)

GHC, when you use the -O option to optimize the compiled program, has this rule baked into it:

map f (map g xs) = map (f . g) xs

This means that if it sees nested uses of map, it can reduce them to one pass over the list. Using that:

head (doubleMe (doubleMe (doubleMe [1, 2, 3])))
  == head (map (*2) (map (*2) (map (*2) [1, 2, 3])))
  == head (map ((*2) . (*2) . (*2)) [1, 2, 3])
  == head (map (\x -> ((x*2)*2)*2) [1, 2, 3])
  == head (map (\x -> ((x*2)*2)*2) (1 : [2, 3]))
  == head (((1*2)*2)*2 : map (\x -> ((x*2)*2)*2) [2, 3])
  == ((1*2)*2)*2

---

EDIT: There's clearly a lot of confusion on the topic of one pass vs. three passes in the answers to this question. I'll throw my lot in.

Simple lazy evaluation (as shown in my second example evaluation) doesn't change the number of passes. If we evaluate something like print (doubleMe (doubleMe (doubleMe [1, 2, 3]))), lazy and eager evaluation will do the same amount of work, but in different orders. Let's write the values of the nested expressions and line up the list elements, like this:

                      doubleMe [1, 2, 3] = [2,  4,  6]
           doubleMe (doubleMe [1, 2, 3]) = [4,  8, 12]
doubleMe (doubleMe (doubleMe [1, 2, 3])) = [8, 16, 24]

Now, if we do something like print (doubleMe (doubleMe (doubleMe [1, 2, 3]))):

1. Eager evaluation will attack this row-by-row. First it will compute the whole list [2, 4, 6], then the list [4, 8, 12], then the list [8, 16, 24], and finally it will print the last list.
2. Lazy evaluation attacks this column-by-column. First it will compute the 2 in the first list, then the 4 in the second list, then the 8 in the first list, and print the 8; then compute the 4 in the first list, the 8 in the second list, and so on.

If you're printing the list, since that requires computing all of the elements, it's (more or less) the same amount of work and memory in either case. In the head (doubleMe (doubleMe (doubleMe [1, 2, 3]))) example, however, lazy evaluation does less work.

And the final, "fusion" example (the one using map f . map g == map (f . g)) does less work than the two others, because it's truly one pass. But that's not because of laziness, that's because purity allows for more aggressive optimization.

Answer 3

The evaluation strategy are different.

In the imperative world, the body of the function is evaluated only after the argument has been fully evaluated. Then considering your example.

-- double1 = double2 = double3 = double  
double3 ( double2 ( double1 [1,2,3] ) )  

Initially to evaluate double3, we must evaluate double2
To evaluate double2, we must evaluate double1
To evaluate double1, we must evaluate [1,2,3]
But [1,2,3] do not need to be evaluated, then we can start the evaluation of double1
Then double1 ([1,2,3]) is evaluated to [2,4,6] and passed to the double2
Then double2 ([2,4,6]) is evaluated to [4,8,12] and passed to the double3
Finally the evaluation of double3 can start and return [8,16,24]

double3 ( double2 ( double1 [1,2,3] ) )  
double3 ( double2 [2,4,6])  
double3 [4,8,12]  
[8,16,24]

For a lazy language like haskell to evaluate a function we do not need to wait the fully evaluation of its arguments. Then if a chunk of data has been produce during the evaluation of the argument, then evaluation of the function body can start.

Putting this to the example.

double3 ( double2 ( double1 [1,2,3] ) )
double3 ( double2 [2] ( double1 [2,3] ) )
double3 [4]( double2 [4] ( double1 [3] ) )
[8] double3 [8] ( double2 [6] )
[8,16] double3 [12]
[8,16,24]