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 it1. 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):

Using the list:
  
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:

  1. foldr (+) 0 [1,2,3,4]
  2. 1 + foldr (+) 0 [2,3,4]
  3. 1 + (2 + foldr (+) 0 [3,4])
  4. 1 + (2 + (3 + foldr (+) 0 [4]))
  5. 1 + (2 + (3 + (4 + foldr (+) 0 [])))
  6. 1 + (2 + (3 + (4 + 0)))
  7. 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

  1. foldl (+) 0 [1,2,3,4]
  2. foldl (+) (0+1) [2,3,4]
  3. foldl (+) ((0+1)+2) [3,4]
  4. foldl (+) (((0+1)+2)+3) [4]
  5. foldl (+) ((((0+1)+2)+3)+4) []
  6. (((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:

  1. foldl' (+) 0 [1,2,3,4]
  2. foldl' (+) 1 [2,3,4]
  3. foldl' (+) 3 [3,4]
  4. foldl' (+) 6 [4]
  5. foldl' (+) 10 []
  6. 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

Comments

comments powered by Disqus