Laziness and Infinite Data

Evaluation on demand

Most languages are strict: when you write f(g(x)), g(x) is fully computed first, then handed to f. Haskell is, by default, lazy (more precisely: non-strict, using a specific technique called call-by-need): an expression is not evaluated until — and unless — its value is actually demanded, and once evaluated, the result is remembered so it’s never recomputed.

Under the hood: expressions as graphs

That last clause — “remembered so it’s never recomputed” — is worth taking apart mechanically, because it’s the entire reason call-by-need earns its name over the more wasteful call-by-name (recompute every time, remember nothing).

A Haskell expression isn’t stored as flat text; GHC represents it as a graph — boxes for function applications, arrows pointing to their arguments. Any part of that graph matching the left-hand side of some function’s definition is a redex (“reducible expression”): a piece ready to be rewritten according to that function’s rule.

square :: Int -> Int
square x = x * x

ghci> square (1 + 2)
9

This is precisely what separates lazy evaluation from naively rewriting text. A purely textual substitution of square (1+2) into (1+2) * (1+2) really would compute 1 + 2 twice — once per occurrence. The graph never makes that mistake: x is one node in memory, referenced from two places, and reducing it once is visible from both references at once. This sharing is exactly what “the result is remembered” meant a paragraph ago — not a special case, but the graph’s ordinary behavior.

This is easiest to see by trying to break it:

ghci> let x = 1 `div` 0        -- division by zero — normally an error
ghci> let pair = (x, "hello")  -- no error yet: x was never DEMANDED
ghci> snd pair
"hello"                        -- still no error — we only ever asked for snd

The div by zero never happens, because nothing ever forced fst pair to be evaluated. In a strict language this program would crash immediately; in Haskell it runs fine, because a binding is a promise to compute a value if asked, not a command to compute it now.

The all-important consequence: infinite lists are just… lists

Because nothing is computed until demanded, there’s no rule against defining a list with infinitely many elements. It only becomes a problem if you ask for all of it at once.

allPositiveIntegers :: [Integer]
allPositiveIntegers = [1..]
-- equivalently: allPositiveIntegers = 1 : map (+1) allPositiveIntegers

That commented-out equivalent is worth pausing on, because it’s not just a list that happens to be long — it’s a list whose own definition refers to itself. The very purest version of that idea is a value like ones = 1 : ones, which as a graph looks genuinely different from any finite list:

allPositiveIntegers’s own self-reference is a close cousin of this, not an identical shape — each step builds a genuinely new cons cell via map (+1) rather than looping back to one single node — but the underlying reason it’s possible at all is the same one ones’s literal cycle makes vivid: a definition is allowed to mention itself, because nothing is forced to “finish” before the definition is accepted as valid. take 5 allPositiveIntegers walks five such steps and stops; only a function that genuinely demands an end, like length, would run forever.

ghci> take 5 allPositiveIntegers
[1,2,3,4,5]

allPositiveIntegers is a completely ordinary value of type [Integer] — you can pass it to other functions, pattern-match on it, zip it with something else — and none of that forces the whole (impossible) infinite list to be built. Only functions that genuinely need to see “everything,” like length or sum, would loop forever on it, because they demand an answer that doesn’t exist.

Building the primes, honestly

The classic showpiece of laziness is defining the infinite list of prime numbers as a value — not a function you call with a bound, an actual list, exactly the way a mathematician would write $\{2, 3, 5, 7, 11, \dots\}$:

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

ghci> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

ghci> takeWhile (< 100) primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

Read sieve the way a mathematician reads the Sieve of Eratosthenes: take the head of the remaining candidates as prime, then filter every multiple of it out of the rest, and recurse — on a list that, itself, never ends. Each recursive call to sieve demands only as many elements of its input as the next caller demands from it, all the way back up to whatever take 10 or takeWhile asked for at the top. Nothing about this definition mentions a stopping point, because it doesn’t need one — the caller decides how much of “forever” it actually wants to look at.

Laziness enables modularity

Beyond the “wow, infinite lists” party trick, laziness has a quieter, arguably more important benefit: it lets you separate generating data from consuming it, without paying for values you never look at.

firstPrimeOver1000 :: Integer
firstPrimeOver1000 = head (dropWhile (<= 1000) primes)

In a strict language, you’d typically have to write a single fused loop — “generate primes and stop once you find one over 1000” — mixing two concerns together for efficiency’s sake. In Haskell, primes (the generator) and dropWhile (<= 1000) (the consumer) are written completely independently, each as simple and general as possible, and laziness fuses them automatically at runtime: only as many primes get generated as dropWhile and head actually end up demanding.

The tradeoff, briefly

Laziness isn’t free. Building up long chains of unevaluated thunks instead of computing values immediately can, in pathological cases, use more memory than strict evaluation would — a phenomenon Haskell programmers call a “space leak.” Functions like foldl' (the strict variant of foldl) exist specifically to opt back into eager evaluation where it matters.

Thunks, WHNF, and Normal Form

“Unevaluated” has been doing a lot of work in this chapter without ever being pinned down precisely — it’s worth stopping to name the pieces properly, since the next section’s tools (seq, foldl', bang patterns) only make sense once “how evaluated is this?” has real, distinct answers.

A thunk is exactly what a lazy binding actually is underneath: not a value, but a suspended computation — the code needed to produce a value, paired with the environment it needs to run in, sitting in memory doing nothing until something asks for it. let x = 1 + 2 doesn’t compute 3; it builds a thunk that would compute 3, the moment anything forces x. Forcing a thunk runs its code exactly once and then permanently overwrites the thunk with the resulting value — a second demand for x reuses that stored answer rather than recomputing it, which is what makes laziness in Haskell “call-by-need” rather than the more wasteful “call-by-name.”

Once something does force a thunk, there are two genuinely different stopping points, not one:

Weak Head Normal Form (WHNF) stops at the outermost constructor (or lambda) and goes no further. Forcing (1+2, 3+4) to WHNF confirms only that the value is a pair — (,) — full stop; the two expressions inside, 1+2 and 3+4, are left exactly as unevaluated as they started.

Normal Form (NF) means genuinely finished: no thunks anywhere, at any depth, in the whole structure. (3, 7) is in Normal Form; (1+2, 3+4) reduced only to WHNF is not, even though both “look like a pair” from the outside.

Controlling evaluation: seq, WHNF, and the tuple trap

The tool for opting back into strictness is seq:

seq :: a -> b -> b

a `seq` b evaluates a to WHNF — exactly the shallow notion just defined above — and then returns b. For Just (1+2), that means only confirming the value is Just something; the 1+2 inside stays an unevaluated thunk until something forces it specifically.

-- lazy accumulator: builds a chain of thunks, (((0+1)+2)+3)+..., unevaluated
sumLazy :: [Int] -> Int
sumLazy = go 0
  where go acc []     = acc
        go acc (x:xs) = go (acc + x) xs   -- acc + x is NOT forced here!

-- strict accumulator: forces each intermediate sum immediately
sumStrict :: [Int] -> Int
sumStrict = go 0
  where go acc []     = acc
        go acc (x:xs) = let acc' = acc + x
                          in acc' `seq` go acc' xs

sumLazy on a long list builds an enormous, deeply nested chain of unevaluated additions before ever computing anything, risking a stack overflow when that chain is finally forced. sumStrict forces each partial sum immediately with seq, keeping memory use constant. In practice, Data.List’s foldl' does exactly this pattern for you.

Here’s where that shallowness has real teeth: foldl' looks like it should end the space-leak problem for good — and for an accumulator like a bare Int, it does. But the moment the accumulator has more than one field, WHNF’s shallowness bites back.

import Data.List (foldl')

sumAndLength :: Num a => [a] -> (a, Int)
sumAndLength xs = foldl' step (0, 0) xs
  where step (total, count) x = (total + x, count + 1)

This looks strict — it uses foldl', after all — but it still leaks. foldl' forces the accumulator to WHNF at each step, and for a pair, WHNF means only the outer (,) constructor: the tuple itself is forced, but its two fields, total + x and count + 1, are left as unevaluated thunks, exactly as before. Run this over a few million elements and both fields grow an enormous chain of unreduced additions, defeating the entire point of using foldl' in the first place.

The fix is to make the fields themselves strict, not just the tuple that holds them — either with bang patterns in the step function, or, more robustly, with a dedicated strict data type:

-- fix 1: force both fields explicitly, every step
sumAndLength' :: Num a => [a] -> (a, Int)
sumAndLength' xs = foldl' step (0, 0) xs
  where step (!total, !count) x = (total + x, count + 1)

-- fix 2: a genuinely strict pair type -- can never hold an unevaluated field
data Pair a b = Pair !a !b

sumAndLength'' :: Num a => [a] -> (a, Int)
sumAndLength'' xs = done (foldl' step (Pair 0 0) xs)
  where step (Pair total count) x = Pair (total + x) (count + 1)
        done (Pair total count)  = (total, count)

Both work; they differ in how easy they are to get wrong. The bang patterns in sumAndLength' only help at the pattern match in step — forget to bang a field in some other function that also touches this accumulator, and the leak is back. Pair’s bangs are part of the type itself (!a, !b in the data declaration from Base Camp): every value of type Pair a b, wherever it’s constructed, is guaranteed to have both fields already in WHNF, with no way to accidentally construct a lazy one.

Later chapters take laziness as a given rather than dwelling on this further, but it’s worth knowing upfront: “lazy by default, strict when you ask for it” is the actual bargain, not “lazy, full stop” — and “strict” needs to reach all the way down to every field that matters, not just the outermost layer.