Why is lazy evaluation useful?

Question

Mostly because it can be more efficient -- values don't need to be computed if they're not going to be used. For example, I may pass three values into a function, but depending on the sequence of conditional expressions, only a subset may actually be used. In a language like C, all three values would be computed anyway; but in Haskell, only the necessary values are computed.

It also allows for cool stuff like infinite lists. I can't have an infinite list in a language like C, but in Haskell, that's no problem. Infinite lists are used fairly often in certain areas of mathematics, so it can be useful to have the ability to manipulate them.

A useful example of lazy evaluation is the use of quickSort:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

If we now want to find the minimum of the list, we can define

minimum ls = head (quickSort ls)

Which first sorts the list and then takes the first element of the list. However, because of lazy evaluation, only the head gets computed. For example, if we take the minimum of the list [2, 1, 3,] quickSort will first filter out all the elements that are smaller than two. Then it does quickSort on that (returning the singleton list [1]) which is already enough. Because of lazy evaluation, the rest is never sorted, saving a lot of computational time.

This is of course a very simple example, but laziness works in the same way for programs that are very large.

There is, however, a downside to all this: it becomes harder to predict the runtime speed and memory usage of your program. This doesn't mean that lazy programs are slower or take more memory, but it's good to know.

I find lazy evaluation useful for a number of things.

First, all existing lazy languages are pure, because it is very hard to reason about side effects in a lazy language.

Pure languages let you reason about function definitions using equational reasoning.

foo x = x + 3

Unfortunately in a non-lazy setting, more statements fail to return than in a lazy setting, so this is less useful in languages like ML. But in a lazy language you can safely reason about equality.

Secondly, a lot of stuff like the 'value restriction' in ML aren't needed in lazy languages like Haskell. This leads to a great decluttering of syntax. ML like languages need to use keywords like var or fun. In Haskell these things collapse down to one notion.

Third, laziness lets you write very functional code that can be understood in pieces. In Haskell it is common to write a function body like:

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

This lets you work 'top down' though the understanding of the body of a function. ML-like languages force you to use a let that is evaluated strictly. Consequently, you don't dare 'lift' the let clause out to the main body of the function, because if it expensive (or has side effects) you don't want it always to be evaluated. Haskell can 'push off' the details to the where clause explicitly because it knows that the contents of that clause will only be evaluated as needed.

In practice, we tend to use guards and collapse that further to:

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Fourth, laziness sometimes offers much more elegant expression of certain algorithms. A lazy 'quick sort' in Haskell is a one-liner and has the benefit that if you only look at the first few items, you only pay costs proportional to the cost of selecting just those items. Nothing prevents you from doing this strictly, but you'd likely have to recode the algorithm each time to achieve the same asymptotic performance.

Fifth, laziness allows you to define new control structures in the language. You can't write a new 'if .. then .. else ..' like construct in a strict language. If you try to define a function like:

if' True x y = x
if' False x y = y

in a strict language then both branches would be evaluated regardless of the condition value. It gets worse when you consider loops. All strict solutions require the language to provide you with some sort of quotation or explicit lambda construction.

Finally, in that same vein, some of the best mechanisms for dealing with side-effects in the type system, such as monads, really can only be expressed effectively in a lazy setting. This can be witnessed by comparing the complexity of F#'s Workflows to Haskell Monads. (You can define a monad in a strict language, but unfortunately you'll often fail a monad law or two due to lack of laziness and Workflows by comparison pick up a ton of strict baggage.)

There's a difference between normal order evaluation an lazy evaluation (as in Haskell).

square x = x * x

Evaluating the following expression...

square (square (square 2))

... with eager evaluation:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

... with normal order evaluation:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

... with lazy evaluation:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

That's because lazy evaluation looks at the syntax tree and does tree-transformations...

square (square (square 2))

           ||
           \/

           *
          / \
          \ /
    square (square 2)

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
        square 2

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

... whereas normal order evaluation only does textual expansions.

That's why we, when using lazy evaluation, get more powerful (evaluation terminates more often then other strategies) while the performance is equivalent to eager evaluation (at least in O-notation).