Lazy, eager and greedy evaluation
Tags: functional
Published: 2019-02-21 17:12:26

---
title: Lazy, eager and greedy evaluation
series: Functional fundamentals
published: true
description: 
tags: #fp
---

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:

```haskell
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:
```haskell
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](https://dev.to/jvanbruegge/comment/8k8c) 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

```haskell
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.