Laziness

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

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

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

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
bad­Sum []     = 0
bad­Sum (x:xs) = x + bad­Sum xs

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.