Laziness

This lec­ture is adjusted from Joachim Bre­it­ner.

Strict Evaluation

Haskell is a lazy lan­guage, mean­ing that it employs `lazy eval­u­a­tion`.

Before explain­ing `lazy eval­u­a­tion`, let’s first explain `strict eval­u­a­tion` which most read­ers will likely be more famil­iar with.

`Strict eval­u­a­tion` means that argu­ments to func­tions are eval­u­ated prior to being passed to the func­tions. For exam­ple, con­sider the fol­low­ing func­tion.

```fst x y = x
```

Sup­pose we then called `fst` as fol­lows.

```fst 1 (len [1..9999999999999]) == 1
```

In a strict lan­guage, we must first eval­u­ate the sec­ond argu­ment `(len [1..9999999999999])` to 9999999999999 before exe­cut­ing the call to `fst`, even though the func­tion does not use the sec­ond argu­ment.

While poten­tially inef­fi­cient, one of the ben­e­fits of `strict eval­u­a­tion` is pre­dictabil­ity. In par­tic­u­lar, when using this strat­egy, the pro­gram­mer can eas­ily deter­mine what will exe­cute and when it will exe­cute. This can be impor­tant when try­ing to ana­lyze the com­plex­ity of an algo­rithm.

Another use for strict eval­u­a­tion is in the pres­ence of side effects. For exam­ple, con­sider the fol­low­ing Java exam­ple.

```int x = 4;

int foo() {
x++;
return 2;
}

int bar() {
return x;
}

int baz(int a, int b) {
return b;
}

void main() {
assert baz(foo(), bar()) == 5;
}
```

For this exam­ple, assum­ing Java eval­u­ates argu­ments of func­tions from left to right, we expect `foo()` to exe­cute first, which incre­ments x to 5 (the side effect) and returns 2. Then `bar()` is exe­cuted, return­ing x, which is now 5. Finally, `baz(foo(), bar())` returns 5.

Notice that the strict eval­u­a­tion of `foo()` changed the result of the call `baz(foo(), bar())`, even though `baz` never actu­ally used the result of its first argu­ment. In this case, strict­ness ensures that side-effects of unused func­tion argu­ments are still processed.

Lazy Evaluation

`Lazy eval­u­a­tion` delays eval­u­a­tion of func­tion argu­ments until it is absolutely nec­es­sary to do so. Even fur­ther, it only eval­u­ates those argu­ments as much as is nec­es­sary.

For exam­ple, say we had the same exam­ple from ear­lier in Haskell.

```fst :: a -> b -> a
fst x y = x

len :: [a] -> Int
len []     = 0
len (x:xs) = 1 + len(xs)
```

And we ran the same code.

```Pre­lude> fst 1 (len [1..9999999999999])
1
```

This time, Haskell does not eval­u­ate the sec­ond argu­ment `(length [1..9999999999999])`. This is good, as eval­u­at­ing that argu­ment would take a very long time.

Instead of eval­u­at­ing this sec­ond argu­ment, Haskell passes `fst` the uneval­u­ated expres­sion, which is called a “thunk”. You can think of a “thunk” as a recipe for how to eval­u­ate the argu­ment if need be.

So, the obvi­ous ques­tion is, when do we know we need to eval­u­ate an expres­sion in Haskell?

The `fst` exam­ple above ben­e­fited from lazi­ness because the sec­ond argu­ment was not used. How­ever, as men­tioned at the begin­ning, this is not the extent of lazi­ness. Con­sider the fol­low­ing exam­ple.

```lis­tify :: [a] -> [[a]]
lis­tify x = [x]
```

Let’s com­pare `lis­tify` and `len`. Notice that the two func­tions treat their argu­ment of type `[a]` very dif­fer­ently. `lis­tify` wraps x in an addi­tional list, regard­less of its con­tents while `len` per­forms pat­tern match­ing on it’s argu­ment. As a result, it turns out that `len` will require (some) eval­u­a­tion of its argu­ment while `lis­tify` will not. To see this in action, let’s try an exam­ple.

```Pre­lude> len \$ lis­tify (len [1..999999999999999])
1
```

In order to exe­cute this, `len` exe­cutes with `lis­tify (len [1..999999999999999])` as an argu­ment. `len` pat­tern matches on this input, which indi­cates that we need to exe­cute `lis­tify`. `lis­tify` takes it’s argu­ment `(len [1..999999999999999])` and wraps it in a list, so now we have `[(len [1..999999999999999])]` where the inner call to `len` remains uneval­u­ated because the result of that call is not yet needed. In this case, this trig­gers the sec­ond pat­tern match in `len` which matches `x` with `len [1..999999999999999]` and `xs` with `[]`. We then call `1 + len(xs)` which never uses `x`, so eval­u­a­tion of `len [1..999999999999999]` is never required. The recur­sive call to `len(xs)` requires a pat­tern match on `xs`, which is already eval­u­ated to `[]` and sim­ply returns 0.

Let’s try a slightly more inter­est­ing exam­ple with `take` which fetches the first N ele­ments of a list.

```take :: Int -> [a] -> [a]
take _ []              =  []
take n (x:xs)          =  if n <= 0 then [] else (x : take (n-1) xs)
```

Before using this, let’s first rede­fine our list builder nota­tion `[x..y]` as a func­tion so it is a bit more clear.

```build­List :: Int -> Int -> [Int]
build­List x y = if x > y then [] else x:(build­List (x+1) y)
```

Note that `build­List 1 999999999999999` is equiv­a­lent to `[1..999999999999999]`.

Let’s see how `take` oper­ates lazily by trac­ing out the exe­cu­tion of a call to it.

```take 3 (build­List 1 999999999999999)
take 3 (1:(build­List 2 999999999999999))
1:(take 2 (build­List 2 999999999999999))
1:(take 2 (2: (build­List 3 999999999999999)))
1:2:(take 1 (build­List 3 999999999999999))
1:2:(take 1 (3: (build­List 4 999999999999999)))
1:2:3:(take 0 (build­List 4 999999999999999))
1:2:3:[]
```

Notice that the call to `build­List` is only eval­u­ated up to the value needed by `take` and no more. Lazi­ness is cool.

Dis­claimer: GHC uses a slightly more com­pli­cated pro­ce­dure for lazy eval­u­a­tion known as “graph reduc­tion” which avoids dupli­cate eval­u­a­tion of equiv­a­lent expres­sions and there­fore might dif­fer slightly from the exam­ple above. How­ever, the exam­ple above is a seman­ti­cally equiv­a­lent notion of lazy eval­u­a­tion.

Benefits of Lazy Evaluation

Lazy eval­u­a­tion has a num­ber of ben­e­fits.

1. Infi­nite data struc­tures.

Let’s try a lit­tle exper­i­ment in GHC. Let’s try the fol­low­ing.

```Pre­lude> [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,
38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,...
```

Woah, it just keeps going! This is an infi­nite list, but how is it done? Let’s define our own, called `inf­List`.

```inf­List :: Int -> [Int]
inf­List x = x : (inf­List (x+1))
```

Indeed, `inf­List 1` is equiv­a­lent to `[1..]`.

```Pre­lude> inf­List 1
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,
38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,...
```

So, what’s hap­pen­ing? `inf­List` is exe­cuted the num­ber of times required by the func­tion which called it. In this case, we are using ghci, which calls `show` on the result, which requires eval­u­a­tion of every ele­ment in the list. There­fore, we have an infi­nite loop, iter­a­tively eval­u­at­ing `inf­List` gen­er­at­ing the next ele­ment of the list.

Why is this use­ful? Well, sup­pose we want the first N primes. Let’s use infi­nite lists to achieve this. First, let’s define some helper func­tions.

```fac­tors :: Int -> [Int]
fac­tors n = [i | i <- [1..n], n `mod` i == 0]

is­Prime :: Int -> Bool
is­Prime n = fac­tors n == [1,n]
```

`fac­tors` com­putes the fac­tors of a num­ber and returns them in a list and `is­Prime` deter­mines if a num­ber is prime by deter­min­ing if its fac­tors are sim­ple 1 and itself.

Let’s use these to define all the primes.

```primes = [ i | i <- [1..], is­Prime i]
```

Finally, let’s define a func­tion the first N primes.

```first­NPrimes :: Int -> [Int]
first­NPrimes n = take n primes
```

Let’s check it out!

```Pre­lude> first­NPrimes 100
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,
163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,
241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,
337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,
431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,
521,523,541]
```

2. Effi­ciency

Lazy eval­u­a­tion can offer effi­ciency ben­e­fits as it avoid unnec­es­sary eval­u­a­tion. We saw this ear­lier. Another pow­er­ful exam­ple is the `if` func­tion. As `if` is pre-defined in Haskell, I will cre­ate my own which I call `if’`.

```if' :: Bool -> a -> a -> a
if' True  x _ = x
if' False _ y = y
```

Notice that our defin­tion of `if2` will only ever require eval­u­a­tion of one of the branches of the if state­ment. This is built into the func­tion via lazi­ness and as a result we get it for free!

3. Purity(?)

Lazy eval­u­a­tion works well with pure lan­guages. I sup­pose it’s arguable that purity is a ben­e­fit, as you could also view it as “lazi­ness does not work well with side effects.” How­ever, I like purity, so I’m going to view it as a plus that lazy eval­u­a­tion pushes us away from impure lan­guages. Let’s return to the Java exam­ple from the first sec­tion. Give it another look to refresh your­self.

If Java were lazy, nei­ther `foo()` nor `bar()` would be eval­u­ated ini­tially. Instead, we would enter the body of `baz`. We then reach the state­ment `b` which we must eval­u­ate. We real­ize we need the actual val­ues of the sec­ond argu­ment. We eval­u­ate the call `bar()` which returns 4, and thus `baz(foo(), bar())` returns 4. Note, this is dif­fer­ent from the value of 5 that is returned from stan­dard Java as `foo()` is never eval­u­ated, and there­fore its side-effect is never processed.

While there is noth­ing explic­itly wrong with lazy Java, one can imag­ine that rea­son­ing about the behav­iour of a pro­gram with side-effects and lazi­ness would be very dif­fi­cult. Debug­ging would be a night­mare!

I sup­pose this leads well into the down­sides of lazi­ness...

Consequences of Laziness

1. Effi­ciency

What?! I thought the whole point of lazi­ness was effi­ciency?! Well, you’re mostly right, but lazi­ness does come with trade­offs. Every­time a func­tion argu­ment is not eval­u­ated, it must get wrapped in a “thunk” which takes mem­ory. This repeated process can add up, adding huge mem­ory over­head for a pro­gram and caus­ing it to slow down unex­pect­edly. Let’s con­sider an exam­ple.

```bad­Sum :: Num a => [a] -> a
```

Why is `bad­Sum` bad? Well, it’s not tail-recur­sive, which means you need to keep around all of the pre­vi­ous stack frames. This will not work well for long lists. Let’s make a bet­ter one.

```good­Sum :: Num a => [a] -> a
good­Sum = go 0
where go acc []     = acc
go acc (x:xs) = go (x + acc) xs
```

`good­Sum` is good, right? Almost. Lazi­ness is going to rear its (some­times) ugly head.

Let’s con­sider the eval­u­a­tion of a call to `good­Sum`.

```good­Sum [1,2,3,4]
go 0 [1,2,3,4]
go (1 + 0) [2,3,4]
go (2 + (1 + 0)) [3,4]
go (3 + (2 + (1 + 0))) [4]
go (4 + (3 + (2 + (1 + 0)))) []
(4 + (3 + (2 + (1 + 0))))
(4 + (3 + (2 + 1)))
(4 + (3 + 3))
(4 + 6)
10
```

Huh, well that didn’t seem to help. `good­Sum` still waited till the end to eval­u­ate the addi­tion, mean­ing we have to keep cre­at­ing big­ger and big­ger “thunks” to hold the uneval­u­ated por­tions. This will also not work well for big lists.

Luck­ily, Haskell gives us a way to force strict eval­u­a­tion. Let’s see it at work.

```strict­Sum :: Num a => [a] -> a
strict­Sum = go 0
where go acc []     = acc
go acc (x:xs) = acc `seq` go (x + acc) xs
```

`seq` has type `a -> b -> b`. It forces the eva­lu­tion of its first argu­ment, and then returns its sec­ond argu­ment. In this case, it forces the eval­u­a­tion of the accu­mu­la­tor at each recur­sive call. We now get the fol­low­ing.

```strict­Sum [1,2,3,4]
go 0 [1,2,3,4]
go (1 + 0) [2,3,4]
go (2 + 1) [3,4]
go (3 + 3) [4]
go (4 + 6) []
(4 + 6)
10
```

2. Under­stand­ing eval­u­a­tion is dif­fi­cult!

As described above in the con­text of “side-effects,” under­stand­ing the exact eval­u­a­tion of lazily-eval­u­ated pro­grams can be quite dif­fi­cult. This can make deter­min­ing prop­er­ties like algo­rith­mic com­plex­ity quite chal­leng­ing.