# Haskell - Laziness

Haskell is a non-strict, or *lazy*, language. This means it evaluates expressions only when it needs their results.

Laziness is one of the things that make Haskell special – really special. Lazy evaluation allows easy handling of *infinite* data-structures.

Lets look at a few infinite examples. The most simple one is the list of all integers

`[1..]`

.

That’s it^{1}. Another example – containing all odd integers looks like

`[1,3..]`

.

Another way to define a list of all odd integers is

`filter odd [1..]`

**This** is laziness at work. How is it possible to work with infinite lists? How can we filter an infinite list? The answer is simple: we do only what we have to do! The expression `filter odd [1..]`

doesn’t do **anything** but to tell the compiler “*if we need a value from that list, this is how it is computed*”.

`print $ take 10 $ filter odd [1..]`

computes the first 10 numbers of the list, and prints it to stdout (try to omit “take 10” from the expression).

The `$`

operator saves us from parentheses. The above example could easily be written as `print (take 10 (filter odd [1..]))`

. If you’re not very sure about precedences stick with the parentheses, I tend to write my code using parentheses and rewrite it using `$`

afterwards.

## Fibonacci

A popular example for infinite lists is the Fibonacci row, it is easily defined as

` ````
fib :: [Integer]
fib = 1 : 2 : zipWith (+) fib (tail fib)
```

(zipWith takes two lists, and generates a new list by combining each pair of elements into a new one).

The definition of the list is **recursive**, another nice property of laziness – you couldn’t do that in a strict language! Please don’t be confused by the illustration – the three lists are the **same** list!

Obviously we wouldn’t use that list for real work using Fibonacci numbers – it would require too much memory…

If we’d like to generate all Fibonacci number the above definition is the best we can do, **but**, if we’d like to get a specific Fibonacci number, we’d rather take another definition:

` ````
fib :: Int -> Integer
fib n = fibHlpr n 1 2
where
fibHlpr 0 a _ = a
fibHlpr 1 _ b = b
fibHlpr n a b = fibHlpr (n-1) b (a+b)
```

This is a iterative process. Let’s compare the profiling of the two methods to compute the 100000st Fibonacci number:

Using the option `+RTS -hc`

for profiling generates a graph of the memory usage on the heap (see the documentation) this reveals that **both** versions take about 600k of heap:

Using lists:

Using the iterative process:

Another profiling option reveals statistics for the garbage-collector (parameter `-S`

):

` ````
604,159,196 bytes allocated in the heap
123,180,084 bytes copied during GC (scavenged)
81,007,200 bytes copied during GC (not scavenged)
4,234,128 bytes maximum residency (164 sample(s))
1134 collections in generation 0 ( 0.95s)
164 collections in generation 1 ( 0.57s)
11 Mb total memory in use
%GC time 50.1% (48.6% elapsed)
Alloc rate 399,083,404 bytes per MUT second
Productivity 49.8% of total user, 47.1% of total elapsed
```

Using the iterative process:
` ````
602,528,044 bytes allocated in the heap
114,819,512 bytes copied during GC (scavenged)
80,816,248 bytes copied during GC (not scavenged)
4,017,816 bytes maximum residency (167 sample(s))
1131 collections in generation 0 ( 0.95s)
167 collections in generation 1 ( 0.58s)
11 Mb total memory in use
%GC time 50.2% (48.6% elapsed)
Alloc rate 397,003,108 bytes per MUT second
Productivity 49.8% of total user, 47.0% of total elapsed
```

So, the new conclusion is, that both versions are nearly equivalent – something I haven’t seen coming.

This is another example of **premature optimization**, I thought that the infinite list is a problem, but obviously profiling proved me wrong, **really** wrong!

For computing specific Fibonacci numbers we should really use the formula shown in SICP, but precision gets an issue using non-integrals… .

## Downside

Laziness has its downsides too, sometimes it requires quite a lot of memory. But, as I’ve mentioned in the first article, Haskell is incredibly flexible and we can easily force strict evaluation – look at this somewhat outdated article for examples, or at this entry at the Haskell Wiki.

Other performance tweaks can be found here.

### foldl, foldr, and foldl’

Laziness’ problems are best illustrated using foldr, foldl, and fold’.

The fold operations “fold” a list to a single value, for example to generate the sum of a list, we could write:

`foldr (+) 0 [1,2,3,4]`

Until now, nothing happened, but if we evaluate the statement, the following list is generated:

`foldr (+) 0 [1,2,3,4]`

- 1 +
`foldr (+) 0 [2,3,4]`

- 1 + (2 +
`foldr (+) 0 [3,4]`

) - 1 + (2 + (3 +
`foldr (+) 0 [4]`

)) - 1 + (2 + (3 + (4 +
`foldr (+) 0 []`

))) - 1 + (2 + (3 + (4 + 0)))
`1 + (2 + (3 + (4 + 0)))`

And **after** that, all the additions are carried out.

`foldl`

works the other way around:

`foldl (+) 0 [1,2,3,4]`

generates

`foldl (+) 0 [1,2,3,4]`

`foldl (+) (0+1) [2,3,4]`

`foldl (+) ((0+1)+2) [3,4]`

`foldl (+) (((0+1)+2)+3) [4]`

`foldl (+) ((((0+1)+2)+3)+4) []`

`(((0 + 1) + 2) + 3) + 4`

Again, **after** we build the list of additions we evaluate these, so the space requirement for foldr and foldl is O(n). That’s where foldl’ comes in, it is a **strict** version of foldl (it makes no sense to implement a strict version of foldr, try to figure out why).

`foldl' (+) 0 [1,2,3,4]`

generates no list of operations to carry out, but carries them out immediately. So The steps required by foldl’ are:

`foldl' (+) 0 [1,2,3,4]`

`foldl' (+) 1 [2,3,4]`

`foldl' (+) 3 [3,4]`

`foldl' (+) 6 [4]`

`foldl' (+) 10 []`

`10`

Use `foldl'`

if you are sure that you have to carry out **all** operations, for example for sums or products.

^{1} The notation `[a..b]`

generates the list of all integers between `a`

and `b`

, obviously we can leave out the upper bound to generate infinite lists.

**Update:** There are some comments on Reddit explaining and clarifying some points. I **had** to update the article because I simply screwed up with the first version. Thanks for all suggestions (now I wish my blog could handle comments too).

About the use of language: it is impossible to sharpen a pencil with a blunt axe. It is equally vain to try to do it with ten blunt axes instead.

— Edsger Dijkstra