Before you begin
Why this matters
Most of the time you can ignore when Haskell computes things. You cannot ignore it when a value would fail, when a total grows slowly in memory, or when you want to know why a program printed half a line. Following demand lets you answer each of these.
What this helps you reason about
- Predict which expressions a program computes, and in what order the stepper stops.
- Explain why a running total or a map of totals uses more and more memory.
- Choose where to ask for a value early, and where asking early would break the program.
In Python, Java, and JavaScript, a function’s arguments are computed before the function starts, and a variable holds a finished value. Haskell works from the other end. The output needs some values, those values need others, and an expression that nothing needs is never computed. Function calls showed one case: an argument that is never used. This lesson follows demand through a whole program, shows what GHC keeps while it waits, and shows how to ask for a value earlier. Haskell lazy lists and finite demand applies the same rule to the cells of a list.
Already know this? The short version
- The Haskell 2010 Report promises non-strict semantics: an expression is computed only if the result needs it, and error or undefined that nothing needs is harmless. GHC implements this with thunks that are replaced by their value, so a binding is computed at most once per application, and a where binding is computed again in each call.
- A pattern match, seq, and a bang pattern compute a value to weak head normal form: its outer constructor, with the fields still thunks. foldl' forces the accumulator this far at each step.
- A running result that nothing needs during a walk becomes a chain of waiting additions; force each number with a bang or seq, or keep it in a strict field or Data.Map.Strict.
- The section “What goes wrong with demand in real programs?” covers a strict pair that still waits inside, lazy Data.Map values, foldl and lazy helpers on long lists, and a bang that forces a value which may fail.
Words in this lesson (7)
- non-strict evaluation
- The Haskell rule that an expression is evaluated only when its value is needed. A binding that nothing needs is never evaluated. GHC implements the rule as lazy evaluation: a named value is usually computed at most once and then shared.
- thunk
- GHC’s stored description of work that has not happened yet. When the value is needed, GHC runs the work and replaces the thunk with the result.
- seq
- The function seq a b, often written a `seq` b. It computes a to weak head normal form, then gives b. It is how Haskell code asks for a value before the result needs it.
- bang pattern
- A ! in front of a pattern, such as !total. When the equation is tried, the value is computed to weak head normal form first. GHC 9.0 needs {-# LANGUAGE BangPatterns #-} at the top of the file.
- strict left fold
- foldl' from Data.List. It walks a list from the left and computes the running result at each step, so no additions wait.
- weak head normal form
- A value computed as far as its outer constructor and no further, such as Just _ or (_, _) with the parts still waiting. A number in weak head normal form is fully computed.
- space leak
- Memory a Haskell program keeps for longer than its results need, often because a thunk still refers to a large value.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / Demand
Which expressions does a result need?
A Haskell program computes what its output needs, and nothing else. putStrLn line needs line. line may be built from a function result, and that result needs the parts that its right side uses. Follow these needs from the output backwards, and you have every expression that runs. This is non-strict evaluation, which Function calls met as an argument that is never computed.
Two standard values make this visible. error "message" is a value of any type that stops the program with that message when it is computed. undefined is the same, with the message Prelude.undefined. Either one is safe in a program as long as nothing needs it.
Below, lunchLine receives budget but never uses it, so the error inside budget never runs. The order of the stops follows demand too: the text "Design" is printed before guests is computed, because show guests is needed only after the first part of the text.
lunchLine :: String -> Int -> Int -> String
lunchLine team guests budget = team ++ ": " ++ show guests ++ " guests"
-- budget = error "budget not approved"
-- lunchLine "Design" 6 budget is "Design: 6 guests"
-- budget is never computedAn expression is computed only when something the output needs uses it; a value that would fail is harmless while nothing needs it.
Coming from Python: Python computes every argument before the call, so f(1, 1 / 0) fails before f starts. In Haskell, f 1 (1 `div` 0) fails only if f uses its second argument.
Precisely: what “needed” means
The Report defines non-strict semantics with ⊥ (“bottom”), the value of a computation that fails or never ends. A function f is strict when f ⊥ is ⊥. lunchLine is strict in team, because ++ looks at its left side first, and not strict in budget. Pattern matching, seq, and primitive operations such as + on Int are what finally demand a value; everything else passes it on unevaluated.
Experiment
Pass a budget that would stop the program
putStrLn needs the text, the text needs lunchLine’s result, and the result is built from team and guests. Nothing in it uses budget, so the error inside budget is never computed. After the edit, the text needs show budget, and computing budget runs error.
Why it matters Read a Haskell program from the output backwards: an expression runs only when something that is needed uses it.
budget is an error that stops the program if it is ever computed. Predict whether the program prints its line. Then change line 2 to lunchLine team guests budget = team ++ ": " ++ show budget and predict again.
lunchLine :: String -> Int -> Int -> String
lunchLine team guests budget = team ++ ": " ++ show guests ++ " guests"
main :: IO ()
main = do
let guests = 4 + 2 :: Int
budget = error "budget not approved" :: Int
putStrLn (lunchLine "Design" guests budget)
What to look for
Each stop shows one place, such as Main.lunchLine, not a list of frames. At the stops in lunchLine, the variables list team and guests but not budget: GHCi lists only the names that the expression at the stop uses, and a value not yet computed shows as _ (unevaluated). The output grows in parts, Design, then Design: , and only then does GHCi stop on line 6 to compute guests. The run prints Design: 6 guests. After the edit, the output stops at Design: , GHCi stops on line 7 to compute budget, and the run ends with *** Exception: budget not approved.
Expected output
Design: 6 guests03 / seq and bang patterns
How do you ask for a value before it is needed?
Sometimes waiting is the problem. A running total that nothing needs during a walk becomes a chain of additions: ((0 + 4) + 2) + 5. Each addition is a thunk that holds the one before it. On a long list, that chain uses memory for every element, and it is added up only at the end. Haskell recursion and collection transformations named this as the waiting additions of foldl. This section shows how to stop them.
seq a b computes a, then gives b. Use it to say “compute this now”: total `seq` tally (total + guests) rest computes total before the next step.
A bang pattern says the same thing in the pattern. tally !total (guests : rest) computes total whenever the equation is tried. Bang patterns are a GHC extension. A line {-# LANGUAGE BangPatterns #-} at the top of the file turns it on; a line between {-# and #-} is a pragma, an instruction to the compiler.
foldl' from Data.List is the strict left fold: it does the same for the running result of a fold.
{-# LANGUAGE BangPatterns #-}
tally :: Int -> [Int] -> Int
tally total [] = total
tally !total (guests : rest) = tally (total + guests) rest
-- the same with seq:
-- tally total (guests : rest) =
-- total `seq` tally (total + guests) restForce a running result at each step with a bang pattern, seq, or foldl'; otherwise the steps wait as a chain of thunks.
Coming from Java: A Java stream waits until a terminal operation, but each number it then produces is computed at once. In Haskell, a number can itself wait, as an addition that has not run.
Precisely: what seq promises
The Report defines seq by its result: seq ⊥ b = ⊥, and seq a b = b when a is not ⊥. It does not promise that a is computed before b; GHC also has pseq for that. In practice GHC computes a first. A bang pattern !x in an equation means the same as using x `seq` on the right side.
Experiment
Watch a running total wait
Nothing asks for total while tally walks the list, so each addition waits inside the next one. !total asks for total each time the second equation matches, so the chain never grows longer than one addition.
Why it matters A running total that nothing needs during the walk becomes a chain of additions. Force it at each step with a bang pattern, seq, or foldl’.
tally adds the guests of three teams. Predict what total shows at each stop on line 5. Then change line 5 to tally !total (guests : rest) = tally (total + guests) rest and predict again.
{-# LANGUAGE BangPatterns #-}
tally :: Int -> [Int] -> Int
tally total [] = total
tally total (guests : rest) = tally (total + guests) rest
main :: IO ()
main = print (tally 0 [4, 2, 5])
What to look for
total shows 0 at the first stop and _ (unevaluated) at the next two: each total + guests waits as a thunk. At the stop on line 4, the [] equation, total is still _ (unevaluated). Only then, when print needs the result, does GHCi stop on line 5 three more times, with guests = 5, 2, and 4: the waiting additions run, newest first. After the edit, total shows 0, 4, and 6 at the stops on line 5, because each addition runs before the next step starts. On line 4, total is still _ (unevaluated): the last addition, 6 + 5, waits until print needs it.
Expected output
1104 / Weak head normal form
How far does a pattern match or seq compute a value?
Pattern matching computes a value only as far as the pattern needs. To match Just _ or Nothing, GHC must know which constructor the value has. It does not compute what is inside. A pair is the same: the pattern (teams, guests) needs the pair, not the two numbers in it.
A value computed as far as its outer constructor is in weak head normal form. Just (error "room size unknown") is in weak head normal form: it is a Just, and the error inside never runs unless something uses it. seq, bang patterns, and foldl' all stop here. A number has no inside, so a number in weak head normal form is fully computed.
This is why a bang on a pair does not stop the waiting: the pair is already a pair. Put the bang on each number instead, (!teams, !guests), or make the fields of a record strict. A data declaration such as data Lunch = Lunch !Int !Int has strict fields: building a Lunch computes both numbers.
roomLine :: Maybe Int -> String
roomLine (Just _) = "room booked"
roomLine Nothing = "no room yet"
-- roomLine (Just (error "room size unknown")) is "room booked"
-- (error "x", 3) `seq` "ok" is "ok"A pattern match, seq, and a bang compute a value only to its outer constructor; force the parts separately when they must not wait.
Precisely: normal forms
Normal form means fully computed, all the way down. Weak head normal form stops at the outer constructor, a lambda, or a partly applied function. The deepseq package, which comes with GHC, provides deepseq and force for normal form; they walk the whole value every time, so they cost time on large values.
Experiment
Force a pair and look inside it
!(teams, guests) asks for the pair, and a pair is already a pair before its numbers are computed. A bang on each name asks for each number. Both are weak head normal form: the bang computes a value only as far as its outer constructor.
Why it matters To keep numbers inside a pair or a record from waiting, force the numbers themselves, not only the value that holds them.
This tally has a bang in front of its pair. Predict what teams and guests show at the stops on line 6. Then change line 5 to tally (!teams, !guests) (size : rest) = and predict again.
{-# LANGUAGE BangPatterns #-}
tally :: (Int, Int) -> [Int] -> (Int, Int)
tally sofar [] = sofar
tally !(teams, guests) (size : rest) =
tally (teams + 1, guests + size) rest
main :: IO ()
main = print (tally (0, 0) [4, 2, 5])
What to look for
teams and guests show 0 at the first stop, then _ (unevaluated) at the next two, as if there were no bang. On line 4, sofar shows (_ (unevaluated),_ (unevaluated)): a pair whose two numbers are still waiting. The output shows ( before GHCi goes back to line 6 to run the waiting additions, and the run prints (3,11). After the edit, the stops on line 6 show teams = 1 and guests = 4, then teams = 2 and guests = 6. On line 4, sofar still shows (_ (unevaluated),_ (unevaluated)): the last step’s two additions wait for print.
Expected output
(3,11)05 / In production
What goes wrong with demand in real programs?
Four mistakes with demand are common in real Haskell code.
A strict pair or record that still waits inside. A loop with !(count, total), or foldl' over a pair, forces the pair and nothing in it. Memory grows with every element. Force each number, or use strict fields.
Lazy values in a Data.Map. Map.insertWith (+) and Map.fromListWith (+), which builds a map from key and value pairs and combines values with the same key, store each sum as a thunk. A counter map updated a million times keeps a million waiting additions. Import Data.Map.Strict instead: it has the same functions, and it computes each value when it stores it. Like seq, it stops at weak head normal form.
foldl or a lazy helper on a long list. foldl (+) 0 and a hand-written accumulator without a bang both build the chain from the forcing section. Use foldl' or a bang pattern on the accumulator. Reachability and garbage collection, a later lesson, measures this memory.
A bang that forces a value which may fail. A bang added “for speed”, such as !average = total `div` count in a where, computes the average before any guard is tried. For a count of 0, the program stops with divide by zero, even when the guard for 0 would never have used the average. Force only values that every path needs.
import qualified Data.Map.Strict as Map
-- each total is computed when it is stored
totals :: [(String, Int)] -> Map.Map String Int
totals orders = Map.fromListWith (+) ordersForce the numbers, not only what holds them; use Data.Map.Strict for totals; never force a value that some path does not need.
Experiment
Look for waiting sums inside a map
The lazy Data.Map stores whatever expression it is given, so a combined value waits as a thunk. Data.Map.Strict computes each value before it stores it, to weak head normal form.
Why it matters For counters and totals in a map, import Data.Map.Strict. Its values are computed when they are stored.
fromListWith (+) builds a map and adds the guests of a team that appears twice. Predict what the map holds for Design at the stop on line 8. Then change line 1 to import qualified Data.Map.Strict as Map and predict again.
import qualified Data.Map as Map
main :: IO ()
main = do
let orders = [("Design", 4), ("Sales", 2), ("Design", 5)]
guests = Map.fromListWith (+) orders :: Map.Map String Int
print (Map.size guests)
print (Map.lookup "Design" guests)
What to look for
At the stop on line 8, guests shows Data.Map.Internal.Bin 2 "Design" _ (unevaluated) Data.Map.Internal.Tip ....: this is the map’s internal tree, and .... is where GHCi stops printing. The key "Design" is there, but its value, 5 + 4, is a waiting addition. The run prints 2, then Just 9, when lookup and print need the value. After the edit, the same stop shows Bin 2 "Design" 9: the strict map computed the sum when it stored it. The output is the same.
Expected output
2
Just 906 / Try it
Can you predict what a program computes?
Find what each line needs before you predict.
main :: IO ()
main = do
let seats = [6, 6, error "seat count missing"] :: [Int]
plan = (head seats, sum seats)
print (length seats)
print (plan `seq` fst plan)
What does the program print, and does it stop with seat count missing?
Reveal the reasoning
3, then 6, and the program finishes without the error. length counts the cells of seats and never looks at the numbers inside, so the error is never computed. plan `seq` computes plan only to weak head normal form: a pair with two thunks inside. fst plan then needs head seats, which is 6. sum seats would need the error, but nothing needs sum seats, so it is never computed.
Practice tickets
- HS-601 · The cycle-to-work screen leaves every ride waiting → Free
- HS-602 · The air quality alarm never sounds while the monitor is live → Sign in · Pro
- HS-603 · The snack fund table keeps every payment waiting → Sign in · Pro
Keep exploring
Haskell IO and explicit effects →