Laziness and Infinite Data
Haskell can define AllPositiveIntegers as an honest, infinite list — and find primes among them — because nothing gets computed until you actually ask to see it.
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.
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
ghci> take 5 allPositiveIntegers
[1,2,3,4,5]
Figure: allPositiveIntegers = [1..] really is infinite — but take 5 only ever forces the first five cons cells into existence. Everything past that stays an unevaluated thunk: a suspended computation, sitting there unbuilt, until (and unless) something asks for it.
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.
Laziness doesn’t mean “slow” and it doesn’t mean “eventually gets around to it” — every value is still computed exactly when something needs it, immediately. The word describes when work happens (on demand, rather than eagerly ahead of time), not how fast. This is a genuinely common point of confusion for people coming from “lazy” used as a synonym for “sluggish” in everyday English.
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 :
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.
This particular sieve is elegant but not the asymptotically fastest prime sieve — the nested mod checks against every previously found prime add up. It’s kept here in its classic, textbook form because the point isn’t performance, it’s that “the infinite list of primes” is expressible, directly, as ordinary Haskell with no special machinery. (A proper Sieve of Eratosthenes with early termination and unboxed arrays is one of the standard “now make it fast” exercises once this version clicks.)
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.
This “generate the whole (possibly infinite) space, then let the consumer decide how much to look at” pattern shows up constantly outside Haskell too — Python generators and itertools, Java 8 Streams, and reactive programming libraries like RxJava are all, in effect, retrofitting a limited, opt-in version of laziness onto languages that are strict by default. Haskell is unusual mainly in making this the default way every value behaves, rather than a special API you reach for.
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. 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.”