Lecture 27

COMP105 Lectures 2020-12-17

This lecture is on tail recursion.

Strict Evaluation of `factorial`

fact 1 = 1
fact n = n * fact (n-1)

When calling fact 4 under strict evaluation the computer will compute the following:

* fact 3
* (3 * fact 2)
* (3 * (2 * fact 1))
* (3 * ( 2 * 1))
24

This will make a very large tree of values to be evaluated

Recursion and Memory

Recursion seems to use a lot of memory.

4 * (3 * (2 * fact 1))

This is the call stack:

Each recursive call adds a new value to the stack.
We can only evaluate the stack then we hit a base case.

We will run out of memory if the call stack it too big.

Tail Recursion

This is the solution to the problem with running our of memory.

A function is tail recursive if there is nothing left to do after the recursive call.

If there is something to do after the recursive call then it is not tail recursive.

is_even 0 = True
is_even 1 = False
is_even n = is_even (n-2)

This is tail recursive as there is nothing added to the call stack. We are passing a single value and not generating additional values.

There is nothing left to do after the recursive call.
No call stack is built up.
Less memory is used.

This is an important concept in all languages:

Even for most imperative languages.
Most C compilers will optimize tail recursive calls.

Writing Tail Recursive Functions

We can make functions tail recursive:

By adding an accumulator as an argument.
It is initialized to some value.
Each recursive call modifies it.
Just like for folds and scans.

fact_tail 1 acc = acc
fact_tail n acc = fact_tail (n-1) (acc * n)

factorial n = fact_tail n 1

This is the same function as before but implemented with a helper function that is tail recursive. You can see that it uses a running total so that it doesn’t have to store many values and then add them together later.

No call stack built up, so no problems in strict evaluation.

In lazy evaluation the memory problem is just transferred to the accumulator.

`fact_tail` in Lazy Evaluation

If we call factorial 4 in a lazily evaluated language:

fact_tail 4 1
fact_tail 3 (4*1)
fact_tail 2 (3*4*1)
fact_tail 1 (2*3*4*1)
24

You can see that the memory problem is still here in lazy evaluation.

Fixing `fact_tail`

We can fix this with the $! (strict evaluation) operator.

fact_tail 1 acc = acc
fact_tail n acc = fact_tail (n-1) $! (acc * n)

factorial n = fact_tail n 1

Now there are no memory problems as the accumulator is evaluated strictly.

This is only okay because we know that we are going to evaluate the accumulator for sure.

Left Folds via Tail Recursion

foldl is naturally implemented via tail recursion.

In strict languages, foldl should be preferred over foldr.

foldl f acc []     = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

> foldl (=) 0 [1,2,3,4,5]
15

Strict Left Folds

The previous implementation is strict but will have memory issues in Haskell. foldl' is the strict version of foldl.

It is in the Data.List package.

It is implemented like so:

foldl' f acc [] = acc
foldl' f acc (x:xs) = (foldl' f $! (f acc x)) xs

This will usually use less memory than foldl.

This is saying that f is lazy f acc x is strict and xs is lazy.

Left Folds and Laziness

A left fold can destroy laziness.

We must reach the end of the list to get the accumulator.

This mean that if you’re operating on an infinite list then your program will never terminate.

Here is a binding that generates an infinite list.

> let f = foldr (\ x acc -> x : acc) [] [1..]
> take 4 f
[1,2,3,4
]

If you rewrite this using a left fold then it won’t terminate.

> let g = foldl(\ acc x -> acc ++ [x]) [] [1..]
> take 4 g
<will never terminate>

You shouldn’t use foldl if you are going to evaluate an infinite list.

Summary

foldr

Should be used by default in Haskell.
- Because it preserves laziness.

foldl

There is not real reason to use this in Haskell.

foldl'

Should be used when we know that laziness won’t help.
- If we know that we will fold the entire list.
Can have performance benefits.

Exercises

 sum_helper acc [] = acc
 sum_helper acc (x:xs) = (sum_helper $! (acc + x)) xs
 sum list = sum_helper 0 list

 length_helper acc [] = acc
 length_helper acc (_:xs) = (length_helper $! (acc + 1)) xs
 length list = legnth_helper 0 list

 length = foldl' (\ acc _ -> acc + 1) 0

Strict Evaluation of factorial