Lazy, eager and greedy evaluation

If you're getting into (purely) functional programming, you've probably come across the term "lazy evaluation", or perhaps "eager evaluation".

What they are

In short, in a language that is evaluated lazily, a value is only computed when it is needed.

An example:

foo :: [Int]
foo = replicate 5 1

bar :: Int
bar = head foo

main = putStrLn $ show bar -- print the value of bar

In this program, foo, is not evaluated directly. Instead, the runtime 'remembers' that it is equal to replicate 5 1 in a thunk. It similarly stores a thunk for bar and main in a thunk.

Once main tries to get the value for bar, We know bar equals head foo, and that head matches on the pattern value : _.

With this in mind, we expand foo and get bar = head (replicate 5 1). Since replicate 5 1 does not match the desired pattern value : _, we expand it. replicate is recursively defined as something like:

replicate times value =
  if times == 0
    then []
    else value : replicate (times - 1) value

By evaluating one iteration of replicate, we get bar = head (1 : replicate (5 - 1) 1). This argument to head matches value : _. We can now conclude bar = 1.

In this case, lazy evaluation saves us from having to evaluate the remained of the list foo.

In contrast, eager evaluation fully computes values before they are required.

I can't seem to find the reference for greedy evaluation anymore, so don't take this as gospel, but greedy evaluation is when a value is computed as soon as its arguments are known. Imperative languages are generally greedily evaluated.

Eager and greedy evaluation look a lot alike, but eager evaluation allows to e.g. first create a large workload of values to be evaluated, whereas greedy evaluation would immediately evaluate them. The former can be useful for creating concurrent tasks.

I will ignore greedy evaluation in the remainder of this post.

Strict vs non-strict

Rather than talking about lazy or eager languages, it is better to talk about strict and non-strict languages.
Strict means a value may only be evaluated or not evaluated (at rest), whereas non-strict languages also allow for values to be partially evaluated. As you might expect, strict languages correspond to eager evaluation and non-strict languages correspond to lazy evaluation.

But why are strict and non-strict better properties of a language than lazy and eager? Simply put, how a program is evaluated is fundamentally a property of the compiler, which is responsible for turning a program into something that runs, whereas a language only defines the properties of its constructs.

I am being rather pedantic here though.

Relation to purity

Lazy evaluation requires purity. With side-effects, changing the order of evaluation might change a program's result.

However, purity does not require lazy-evaluation. I've heard Haskell folk say that laziness is great because it enforces purity, so any temptations to introduce side-effects are quelled. To me, this sounds like you don't really want purity, but I digress.

Advantages of laziness

I'm not a big believer in non-strict languages, so I will instead cite a comment by @jvanbruegge to provide a more neutral perspective.

It makes a lot of algorithms easier to express and allows you to treat your algorithm as data structure you traverse (which is pretty cool imo). Also without laziness, some normally trivial identities do not hold.

For example this: head . fmap f = f . head. If f bottoms on the second element in the list, the left will bottom and the right not. In a lazy language both won't.

Advantages of strictness

Because strict languages have simpler value states, they become easier to reason about. In particular, memory management and concurrency can become more complicated. For instance, if we have

let 
  x = ...
  y = ...
in
  f(x, y)

Assuming y does not contain x, in a pure language, we could compute x and y concurrently (the lack of side effects makes pure functions unordered safe for data dependencies).

With non-strictness, however, the expansions of x or y may not terminate even when f(x, y) would, or they may be much longer than necessary.