# Deep Understanding of Fold in Haskell

`fold`

is a very important combinator in functional programming. In Haskell four versions of `fold`

operation
are provided: `foldl`

, `foldr`

, `foldl'`

and `foldr'`

. Now lets take a close look at them. We’ll gain a better
understanding of the underlying principles behind `fold`

operation and learn how to use them correctly and
efficiently in our real world applications.

## Implementation

`fold`

is a higher order function that takes a function and a list as arguments, look at the
detailed implementations of these four `fold`

functions in the
base library.

```
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z0 xs0 = lgo z0 xs0
where
lgo z [] = z
lgo z (x:xs) = lgo (f z x) xs
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
where
go [] = z
go (y:ys) = y `k` go ys
foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' f z0 xs0 = lgo z0 xs0
where lgo z [] = z
lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
foldr' :: (a -> b -> b) -> b -> t a -> b
foldr' f z0 xs = foldl f' id xs z0
where f' k x z = k $! f x z
```

`foldl`

means *left-associative* fold operation, folding up a list form the left to right and `foldr`

are
*right-associative* fold operation. `foldl'`

and `foldr'`

are strict version of `foldl`

and `foldr`

.
We can see that `foldl`

and `foldl'`

are both tail recursion and `foldr`

and `foldr'`

are not.
Because Haskell is a programming language with non-strict evaluation strategy, the lazy version of `foldl`

and `foldr`

will accumulate too many unevaluated **chunks** on heap when the list to fold over is too long.

There’s also a picture from Wikipedia that can illustrate the core feature of `foldl`

and `foldr`

very well:

Another significant difference is that `foldr`

runs forwards while `foldl`

runs backwards. The function
`foldl (flip (:)) []`

can reverse a list while `foldr (:) []`

returns a list unchanged. This is why
`foldr`

can fold over infinite lists while `foldl`

can’t.

## Benchmark

I make a basic benchmark to measure the performance of these four version of fold operation, and the
result of benchmark is corresponded with our knowledge about above detailed implementations of fold
operation. The task is computation summary of an integer sequence `[1..1000000]`

.

```
r = @fold (+) 0 ([1..1000000] :: [Int])
```

All experiments are done using GHC 8.0.1 with `-O2`

optimization on 64bit Windows 10 (CPU: Intel 5600U).

### CPU Usage

I use the criterion which is a well-known framework for executing and analyzing benchmark in Haskell to perform CPU time usage benchmark.

```
Case CPU time
foldl 174.8 ms
foldr 29.23 ms
foldl' 9.806 ms
foldr' 87.38 ms
```

`foldl'`

is the fastest version of these four fold operations. I have also noticed an interesting phenomenon that
`foldr`

with `-O`

optimization is four times slower than using `-O2`

optimization option.

### Memory Allocation

Fpcomplete has developed a very convenient tool called weigh which can measure allocations in Haskell program. The result is as follows:

```
Case Bytes GCs Check
foldl 169,259,440 322 OK
foldr 96,646,080 153 OK
foldl' 95,999,920 186 OK
foldr' 127,999,920 247 OK
```

`foldl'`

use the least memory.

## Why `foldl`

is in the first place ?

Why `foldl`

, rather than `foldl'`

, be placed in the first place, although `foldl`

performs
so poor ? A possible reason is, when Haskell 1.0 was published there’s no `seq`

function
in language standard, there was `foldl`

no choice but to define `foldl`

in a such way. The
`seq`

was introduced in Haskell 1.3. `foldl`

was not changed and mainstream Haskell compiler
added the `foldl'`

function.

## Best Practice

After analysis the principles of fold operation, we can conclude some best practical strategies to improve
performance when use `fold`

operator in Haskell:

- When we are sure that the list to fold is finite, the fold computation will terminate, then
`foldl'`

would be the best choice. `foldr`

is the only fold function that can process infinite lists, when the binary function has the property of short-circuit evaluation (like logical*and*`&&`

and logical*or*`||`

), the computation will terminate. Be careful that`foldr'`

can’t be used to process infinite list.- Under almost all conditions the
`foldl`

combinator has the worse performance both in time usage and memory allocations and shouldn’t be used in production-level code, as the Haskell Wiki says:`foldl`

is rarely the right choice.