Laziness and infinite lists

What laziness means

Haskell does not evaluate an expression when it is written; it evaluates it when its value is needed. Until then the expression sits in memory as a thunk, a computation waiting to run, and an argument that is never demanded is never computed. That is why a function with an unused parameter costs nothing and why a list can be infinite:

take 5 [1 ..] -- [1,2,3,4,5]: the rest is never built head (filter odd [2, 4, 5, 6]) -- 5: the 6 is never touched

The consequence is that a function has to be read as a producer whose consumer decides how much work happens. The lesson on space leaks later shows the other side: a thunk that is built and never forced still takes memory.

Infinite lists

Three Prelude functions build an infinite list from a finite one: repeat and cycle repeat, and iterate applies a function again and again. zip and take decide where to stop:

module Main (main) where ones :: [Int] ones = 1 : ones naturals :: [Int] naturals = [0 ..] fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs) main :: IO () main = do print (take 5 naturals) print (take 6 (cycle [1, 2, 3 :: Int])) print (zip (cycle "ab") [1, 2, 3 :: Int]) print (take 10 fibs) print (take 3 (map (* 2) ones)) print (take 1 (dropWhile (<= 100) naturals))

ghc -Wall -O1 -o infinite infinite.hs
./infinite

[0,1,2,3,4]
[1,2,3,1,2,3]
[('a',1),('b',2),('a',3)]
[0,1,1,2,3,5,8,13,21,34]
[2,2,2]
[101]

fibs refers to itself: every element is the sum of the two before it, and the definition is the recurrence, not a loop. ones is the smallest infinite list, and map (* 2) ones would never finish if take 3 did not stop it. The last line scans the natural numbers until it passes 100 and takes one, which is a search written as a list.

What is forced and what is not

A list element is a thunk and length only counts the cons cells, so a list with an error in an element has a length:

module Main (main) where short :: Bool short = and (False : error "the rest was not forced") keep :: [Int] keep = take 2 (1 : 2 : error "the tail was not forced") main :: IO () main = do print short print keep let _unused = error "a binding nobody asks for" :: Int print (length ([1, 2, 3] ++ [error "no element measured"] :: [Int]))

ghc -Wall -O1 -o forced forced.hs
./forced

False
[1,2]
4

Three different escapes: and stops at the first False, take 2 never reaches the third element, and length never looks inside the cells. The let binding is not demanded at all, so its error never happens. A program with a bug like this compiles and runs, which is why the strictness controls of the next lesson exist.

Zip and takeWhile on two infinite lists

Zipping two infinite lists gives one infinite list of pairs, and takeWhile stops at the first element that fails the test, so a list of pairs can be cut by a condition on the second component:

module Main (main) where pairs :: [(Int, Int)] pairs = zip [0 ..] (map (* 2) [0 ..]) main :: IO () main = do print (take 4 pairs) print (takeWhile (\(_, value) -> value < 10) pairs) print (length (take 1000000 [1 :: Int ..]))

ghc -Wall -O1 -o pairs pairs.hs
./pairs

[(0,0),(1,2),(2,4),(3,6)]
[(0,0),(1,2),(2,4),(3,6),(4,8)]
1000000

The predicate on the pair stops at the first second component that is 10, so the fifth pair is the last one kept. The third line is the other direction: a million elements are demanded on purpose and the count is the proof, and the program still runs in a moment because each element is an integer and not a chain of thunks. A takeWhile whose predicate never fails would never stop; that is the one mistake to avoid with an infinite list.

The cost of a thunk

Laziness is not free. Every unevaluated expression is a heap object with a code pointer and the free variables it needs, and a chain of thunks costs more than the value it will produce. The rules that follow from it:

The default is right for most code: composition and short lists gain from laziness, and a pure function that is never asked never runs. The next lesson adds the annotations that take the choice back where it matters.

Exercises

  1. Build the list of the powers of two with iterate and take ten.
  2. Write primes :: [Int] as a sieve and take the first ten.
  3. Explain why take 3 (repeat 7) finishes but length (repeat 7) does not.
  4. Print the length of a list of ten elements each of which is error "x" and explain the answer.
  5. Rewrite the Fibonacci list with a helper that carries the last two values and compare the two definitions.
  6. Find a takeWhile on an infinite list that never stops and explain what makes a predicate safe.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. When is an expression evaluated in Haskell?

    Answer

    When its value is needed

    Laziness defers evaluation until a consumer demands the value, which is why infinite lists work.

  2. What does take 3 [1 ..] give?

    Answer

    [1,2,3]

    take bounds the infinite list and only three elements are built.

  3. What is a thunk?

    Answer

    An unevaluated expression waiting in the heap

    A thunk is the runtime representation of a computation that has not run yet.

  4. What does this program print? module Main (main) where main :: IO () main = print (take 4 (cycle [1, 2 :: Int]))

    Answer

    [1,2,1,2]

    cycle repeats the two elements and take stops after four.

  5. What does length ([1, 2] ++ [error "x"]) return?

    Answer

    3

    length counts the cons cells and never forces the element that is an error.

  6. What does this program print? module Main (main) where main :: IO () main = print (zip [1, 2 :: Int] "ab")

    Answer

    [(1,'a'),(2,'b')]

    zip pairs the elements by position and the shorter list ends the result.

  7. Why can fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs) work?

    Answer

    Each element is demanded only after the ones it depends on exist

    The definition is productive: taking n elements forces only what those elements need.

  8. What is the danger of laziness in a long fold?

    Answer

    A chain of thunks builds up and uses memory until it is forced

    That is the space leak the strictness and space-leak lessons measure.

  9. What does and (False : error "x") return?

    Answer

    False

    and short-circuits on the first False and never touches the rest of the list.

  10. What does a let binding that is never used cost?

    Answer

    Nothing at run time, because it is never demanded

    The binding is a thunk and the error in it never happens if nothing asks for the value.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev