30.md

Laziness

Laziness is the term that is used most frequently when talking about Haskell evaluation model. A more specific description is call-by-name evaluation with sharing. The latter means that the value of an expression is calculated at most once and reused. The former means that arguments passed to functions do not get evaluated until their value is needed. Let's have a look at some interesting examples. We will use undefined to help us trace the evaluation of our expressions. When undefined is evaluated an exception is thrown.

Try out the following in ghci.

undefined
let a = [1, 2, undefined, 3, 4]
take 2 a
take 3 a
drop 3 a
length a

The last two examples are really interesting. Although we take the element after undefined and traverse the list to calculate its length, no exceptions are thrown. This is because the (:) constructor is evaluated but not its arguments.

Infinite data structures

Laziness allows us to define infinite data structures.

let ones = 1 : ones

How would you evaluate this expression?

1 : ones
1 : (1 : ones)
1 : (1 : (1 : ones))
...

ones is an infinite list of 1s. Still all of the general list functions work on it.

take 20 ones
let twos = (+1) <$> ones
take 10 $ drop 100 twos

In strict languages, it is impossible to express infinite data structures this way since the argument of (:) would be evaluated before the expression (is), resulting in an infinite loop.

Create echo.hs with the following content:

module Main where

main :: IO ()
main = do
  input <- getContents
  putStrLn input

The type signature of getContents is IO String. It creates an IO action that reads from standard input and returns it as a String value, that we print to the screen. Compile and try it out.

Surprisingly getContents does not finish after a newline character, it continues reading from the terminal, at the same time putStrLn prints back to the screen. getContents creates an IO action that creates a lazy String. It reads from the terminal as long as the input is requested. In this case putStrLn asks for the content.

Guess what happens when you run the following code?

module Main where

main :: IO ()
main = do
  input <- getContents
  putStrLn $ take 20 input

Since no more than twenty characters are requested by take, after reading twenty characters it stops reading.

This is a really nice pattern. With lazy data structures we were able to decouple source, computation and sink. Without it, these stages would be composed together inside a loop.

Problems with lazy evaluation

Although laziness can be used to express things elegantly and sometimes it can spare execution of unevaluated expressions, it comes with a price. The runtime system needs to keep in mind how deferred expressions should be evaluated. These are called thunks. If the evaluation is deferred at the wrong place it can consume a lot of memory and after a while the garbage collector will take all the CPU cycles. Finding a bug like this is not an easy task.

Similar problems emerge when streaming data is consumed with a lazy data structure. Since the actual reading is triggered somewhere during the computation, every problem that is caused by the interaction with real world is hard to track down.

Exercises:

• Complete the implementation of Fibonacci numbers. Next should refer to fibo in the solution. This is not an easy exercise and noone would implement Fibonacci numbers like this, but it forces you to think about infinite lists.

fibo = 1 : 1 : next
  where next = ...

-- expected behaviour
take 7 fibo == [1, 1, 2, 3, 5, 8, 13]