Laziness and infinite lists

Thunks and evaluation

An expression is not evaluated where it is written. It becomes a thunk, a description of work, and is forced only when a consumer needs the value:

x = 1 + 2 -- not computed yet y = x * 10 -- still a thunk y -- 30, now both are forced

A thunk is evaluated at most once: the result is stored, so the second use is free. That sharing is why laziness does not repeat work.

Infinite structures

Because nothing is computed until it is needed, an infinite list is a value like any other. The consumer decides how much exists:

ones = 1 : ones naturals = [1..] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) take 5 ones -- [1,1,1,1,1] take 8 fibs -- [0,1,1,2,3,5,8,13]

The Fibonacci line defines the list in terms of itself, and it works because each element depends only on earlier ones. This is the most quoted example of lazy programming for a reason.

Short-circuiting

Boolean operators stop as soon as the answer is known, and folds over an infinite list stop when the combining function ignores the rest:

False && undefined -- False, the second operand never runs True || undefined -- True any (> 100) [1..] -- True, stops at 101 elem 3 [1..] -- True, stops at 3

This is why foldr can work on an infinite list while foldl cannot: the right fold sees the first element before the rest of the structure exists.

When laziness bites

The two surprises are memory and order of effects. A chain of lazy additions builds a tower of thunks, and a lazy read of a file may keep the handle open longer than expected:

-- builds a million thunks before the first result foldl (+) 0 [1..1000000] -- strict version, constant memory foldl' (+) 0 [1..1000000]

The next lesson turns that warning into a set of tools: strict folds, bang patterns, and the profiler that finds the leak.

Next: Strictness and space leaks

Article author: Arthur Isaev