Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 57 ยท Laziness and purity

Lazy Evaluation

Learn how Haskell delays work until a value is needed: thunks, call by need, infinite lists with take, iterate and cycle, and when laziness helps.

Most languages evaluate an argument before calling a function. Haskell does not. An expression is evaluated only when something actually needs its value, and at most once. This is lazy evaluation, and it is one of the two features (with purity) that make Haskell feel different.

Laziness lets you define infinite lists, separate "what to compute" from "how much to compute", and write short definitions that would loop forever in a strict language. It also has costs, which the next lesson, Strictness, Bang Patterns and seq, addresses.

Real Haskell is read-only on this site. The runnable examples use JavaScript generators and thunks as stand-ins for the same idea.

Thunks and call by need

When Haskell sees let x = expensive 10 in ..., it does not run expensive. It stores a thunk: a small object that remembers the expression and its environment. The first time x is demanded, the thunk is evaluated and overwritten with the result. Later uses read that result directly. This strategy is called call by need (lazy evaluation with sharing).

HASKELL
let big = sum [1 .. 1000000]
in  if False then big else 0

big is never needed, so the million additions never happen. Compare with const 1 undefined, which returns 1: undefined is never touched.

Life of a thunk

Created A promise to compute, not the answer.
Demanded Pattern matching or printing needs the value.
Evaluated The expression runs once.
Cached Later uses reuse the result.

Only the first use pays.

1 / 2

What "needed" means

Evaluation is driven by pattern matching and primitive operations. The result is evaluated only to the shallowest form necessary, called weak head normal form (WHNF): the outermost constructor or function. Evaluating [1, 2, undefined] to WHNF just shows a (:) cell; the undefined inside is untouched. Taking length of it works (length never inspects the elements) while sum of it fails.

HASKELL
length [1, 2, undefined]     -- 3
fst (10, undefined)          -- 10

Infinite lists

Because a list cell is only built when demanded, a list can be infinite. You only ever consume a finite part:

HASKELL
naturals :: [Integer]
naturals = [0 ..]

take 5 naturals            -- [0,1,2,3,4]
takeWhile (< 40) (map (^ 2) naturals)   -- squares below 40

A few functions generate infinite lists:

HASKELL
repeat 'x'            -- "xxxxxxxx..."
cycle [1, 2, 3]       -- 1,2,3,1,2,3,...
iterate (* 2) 1       -- 1,2,4,8,16,...

iterate f x gives x, f x, f (f x), .... It is the lazy replacement for a loop where you decide later how many steps you want. With take, takeWhile, zip and !! you pick off what you need. See Higher-Order Functions for iterate in context.

The classic showpiece is the Fibonacci sequence defined in terms of itself:

HASKELL
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Each element depends on the two before it, and laziness makes the self-reference work because zipWith only asks for elements that already exist. Another is the sieve of primes:

HASKELL
primes :: [Int]
primes = sieve [2 ..]
  where
    sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

This is elegant but slow, so it is a teaching example rather than a production prime generator (a list comprehension filtering at each step). It shows how an unbounded stream can be defined first and cut later.

JS Infinite lists with generators (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

JavaScript evaluates the pipeline one element at a time, just like Haskell's lazy lists, so nothing infinite ever gets built. One difference: a Haskell list is a data structure you can traverse again (and the evaluated cells are kept), while a generator is used up once.

Where laziness helps

Modularity. You can write a producer that generates everything and a consumer that stops early, as separate functions:

HASKELL
firstBigSquare :: Integer
firstBigSquare = head (filter (> 1000) (map (^ 2) [1 ..]))

The pieces compose without a manual loop and without computing a million squares: [1 ..] is only evaluated as far as needed, which is 32.

Short-circuiting is just a function. In many languages && and || are built-in special forms. In Haskell they are ordinary functions that happen to ignore their second argument when possible:

HASKELL
False && undefined     -- False
True  || undefined     -- True

So you can define your own control structures as functions:

HASKELL
myIf :: Bool -> a -> a -> a
myIf True  t _ = t
myIf False _ e = e

Only the chosen branch is evaluated. In a strict language this function would evaluate both branches before the call.

Avoiding work. any, elem, head . sort-style definitions and or all stop as early as they can. If you only need the smallest element, a lazy sort can do less than a full sort (though minimum is the better tool).

Knot-tying and memoisation. A lazy structure can reference its own elements, such as a table of results defined in terms of earlier entries, which gives dynamic programming with almost no ceremony.

Where laziness bites

Laziness is not free. Three things to know now and study later:

  • Space leaks. A long chain of unevaluated thunks (for example building (((0 + 1) + 2) + 3) ... lazily) uses memory until forced. The cure is strictness, covered in Strictness, Bang Patterns and seq.
  • Hard-to-predict cost. The expression that fails or is slow may be evaluated far from where it was written. Exceptions from undefined or error appear only when the value is demanded.
  • Lazy I/O. Reading a file lazily can delay errors and keep file handles open (Files, Arguments and Environment).

Purity is what makes laziness safe. If evaluation had side effects, the order in which thunks run would change the program's behaviour. Because expressions have no effects, their values do not depend on when they run (see Purity and Referential Transparency).

GHC does not blindly delay everything. Its strictness analyser spots arguments that will certainly be used and evaluates them early when optimisation is on (-O). Laziness is the semantics; the compiler is free to be eager when the result is the same.

A thunk in a stand-in

A thunk is a function that runs once and remembers its result. This stand-in makes the "evaluate at most once" part visible.

JS Call by need with a memoising thunk (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a thunk?

    A thunk holds an unevaluated expression; evaluating it once overwrites it with its value (call by need).
  2. 2. What does take 3 (iterate (+ 2) 1) return?

    iterate (+ 2) 1 is 1, 3, 5, 7, ... and take 3 demands only the first three elements.
  3. 3. Why is length [1, 2, undefined] equal to 3?

    Evaluation is demand-driven; length needs the structure of the list but not the elements.
  4. 4. Why is purity important for lazy evaluation?

    Order of evaluation does not matter for pure expressions, so the runtime may delay or reorder them safely.

Summary

  • Haskell evaluates an expression only when its value is needed, and at most once (call by need).
  • Delayed expressions are stored as thunks; evaluation goes only as far as weak head normal form.
  • Laziness makes infinite lists such as [0 ..], iterate, cycle and self-referential fibs practical.
  • It helps modularity, makes &&, || and your own control functions ordinary functions, and avoids needless work.
  • The costs are possible space leaks, less predictable evaluation and lazy I/O surprises.
  • Purity is what makes lazy evaluation safe.

Next: Strictness, Bang Patterns and seq.