Functional fundamentals (5 Part Series)
If you're getting into (purely) functional programming, you've probably come across the term "lazy evaluation", or perhaps "eager evaluation".
In short, in a language that is evaluated lazily, a value is only computed when it is needed.
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
main in a thunk.
main tries to get the value for
bar, We know
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
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.
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.
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.
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.
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)
y does not contain
x, in a pure language, we could compute
y concurrently (the lack of side effects makes pure functions unordered safe for data dependencies).
With non-strictness, however, the expansions of
y may not terminate even when
f(x, y) would, or they may be much longer than necessary.