Before you begin
Why this matters
Haskell code uses lists without an end every day: for numbering, for repeating patterns, and for “every next value”. If you can follow which cells a program asks for, you can predict whether it finishes, spot the call that never returns, and see which lists stay in memory.
What this helps you reason about
- Predict how much of a list a program builds, and what is never built.
- Spot a call such as length or filter that never finishes on a list without an end.
- Say when a named list is built once and kept in memory.
In Python or Java, a list holds all of its elements, so a list without an end would never finish building. Python generators and Java streams give values one at a time instead, as a separate kind of object. A Haskell list does both jobs. It is an ordinary list, and each of its cells is built only when some code asks for it. This lesson follows what take, takeWhile, and zip ask for, what is never built, and which functions never finish.
Already know this? The short version
- A list cell is built when some code asks for it, and the rest stays a thunk; GHCi shows it as _ (unevaluated).
- [1 ..], iterate f x, cycle xs, and repeat x have no end that a program reaches; take, takeWhile, head, null, and zip with a finite list stop reading, and a function that gives a cell with : before it asks for the rest makes such a list.
- length, sum, last, reverse, sort, and show need the last cell and never finish on such a list, and filter never finishes once no later element passes; a named list is built at most once, and its built cells stay in memory while the name is still used.
- The section “What goes wrong with lazy lists in real programs?” covers length on an infinite or huge list, a list kept alive by a name, filter where takeWhile was meant, and show on an infinite structure.
Words in this lesson (5)
- list
- A sequence of values of one type, written [12, 7, 31]. It is a chain of cells: each cell holds one element and a link to the rest of the list, and [] is the empty list.
- 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.
- infinite list
- A list in which every cell has a rest, such as cycle [1, 2]. Only the cells that some code asks for are ever built.
- 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 / Cells on demand
When is a list cell built?
Arrays, lists, and vectors showed that a Haskell list is a chain of cells, each with one element and a link to the rest. Haskell bindings and recursive definitions showed that a binding is computed when its value is first needed. This is non-strict evaluation, and lists follow it one cell at a time: a cell is built only when some code asks for it.
[1 ..] counts up from 1 and, in practice, never ends. Writing it builds nothing. take 3 beads gives the first three elements of beads, so it asks for three cells. The rest of beads stays a thunk: work that has not happened yet. No code asks for it, so it is never built.
The stepper shows a list that is partly built in the same way: 1 : 2 : 3 : _ (unevaluated) is three cells, then a rest that is still a thunk.
beads :: [Int]
beads = [1 ..] -- counts up from 1
firstThree :: [Int]
firstThree = take 3 beads -- [1,2,3]
-- take builds three cells of beads; the rest is never builtA list cell is built when some code asks for it; a cell that no code asks for is never built.
Precisely: where [1 ..] ends
[1 ..] is enumFrom 1. For Integer, it has no end. For Int, it stops at maxBound, the largest Int, which is 9223372036854775807 on the stepper’s 64-bit machine, so no program walks to its end. The Haskell 2010 Report specifies non-strict semantics, not when cells are built; building each cell once and keeping it is what GHC does.
Experiment
Count the cells that take builds
print needs firstThree, firstThree needs three cells of beads, and each cell is built when take asks for it. The rest of beads stays a thunk, because no code asks for it.
Why it matters The number of cells built is decided by the code that reads the list, not by the list.
beads has no last element. Predict how many cells of beads exist after print firstThree, and whether head beads builds more. Then change take 3 to take 5 and predict again.
main :: IO ()
main = do
let beads = [1 ..] :: [Int]
firstThree = take 3 beads
print firstThree
print (head beads)
What to look for
Each stop shows one place, such as Main.main.firstThree, not a list of frames. The stops are line 2, line 5 with firstThree shown as _ (unevaluated), line 4, and line 3. On line 6, [1,2,3] has printed, and beads shows 1 : 2 : 3 : _ (unevaluated): three cells, then a rest that nobody has asked for. head beads reads the first cell, so nothing more is built, and 1 prints. After the edit, [1,2,3,4,5] prints, and beads shows 1 : 2 : 3 : 4 : 5 : ....; GHCi writes .... where it stops printing a long value.
Expected output
[1,2,3]
102 / Infinite lists
How can a list without an end be safe to use?
An infinite list is a list in which every cell has a rest. Four standard ways make one:
- [1 ..] counts up from 1.
- iterate f x is x, then f x, then f (f x), and so on. iterate (+ 2) 6 is 6, 8, 10, …; (+ 2) is + with its right side filled in, a function that adds 2, and (< 11) is the test “less than 11”.
- cycle xs repeats the list xs: cycle ["red", "blue", "white"].
- repeat x is x again and again.
An infinite list is safe when the code that reads it stops. take n stops after n elements. takeWhile test stops at the first element that fails the test. head reads one cell. zip pairs two lists and stops when either one ends, so zip [1 ..] numbers any list.
You can make an infinite list yourself. countFrom n = n : countFrom (n + 1) gives a cell with n before it asks for the rest. Nothing asks for the rest until some code reads that far. [1 ..] and iterate work the same way.
rows :: [Int]
rows = iterate (+ 2) 6 -- 6, 8, 10, …
colours :: [String]
colours = cycle ["red", "blue", "white"]
-- take 3 rows is [6,8,10]
-- takeWhile (< 11) rows is [6,8,10]
-- zip [1 ..] ["red", "blue"] is [(1,"red"),(2,"blue")]
-- head (repeat "gold") is "gold"An infinite list is safe while the code that reads it stops: take, takeWhile, head, and zip with a finite list all stop.
Coming from Python: A Python generator gives values on request, but it can be read only once. A Haskell list keeps the cells it has built, and any code can read them again.
Precisely: cycle builds a loop
cycle xs copies the cells of xs once and links the last copy back to the first. The list never ends, but it uses as many cells as xs has, however far it is read. cycle [] has no cells to repeat: the program stops with Prelude.cycle: empty list.
Experiment
Number a repeating pattern with zip
zip builds a pair only when something asks for it, and it stops as soon as either list ends. take 4 asks for four pairs. In the edit, [1 .. 3] ends after three numbers, so zip asks colours for three cells and no more.
Why it matters An infinite list is safe beside a finite one: zip, take, and takeWhile decide where the reading stops.
zip [1 ..] colours pairs two lists that have no end. Predict what take 4 numbered prints, and how many cells of colours exist afterwards. Then change line 4 to numbered = zip [1 .. 3] colours :: [(Int, String)] and line 5 to print numbered, and predict again.
main :: IO ()
main = do
let colours = cycle ["red", "blue", "white"]
numbered = zip [1 ..] colours :: [(Int, String)]
print (take 4 numbered)
print (take 2 colours)
What to look for
After stops on lines 2, 5, 4, and 3, the run prints [(1,"red"),(2,"blue"),(3,"white"),(4,"red")]. On line 6, colours shows "red" : "blue" : "white" : "red" : "blue" : ....: five cells, although take asked for only four. cycle links its last cell back to its first, so the fourth cell is the first one again, and GHCi follows the loop until it stops printing. Then ["red","blue"] prints. After the edit, zip stops when [1 .. 3] ends: the run prints [(1,"red"),(2,"blue"),(3,"white")], and colours shows "red" : "blue" : "white" : _ (unevaluated).
Expected output
[(1,"red"),(2,"blue"),(3,"white"),(4,"red")]
["red","blue"]03 / Whole-list functions
Which functions never finish on an infinite list?
Some functions need the last cell of a list: length, sum, last, reverse, maximum, and sort from Data.List. Printing the whole list with print or show needs it too. An infinite list has no last cell, so these functions never finish. There is no error message and no result. The program keeps reading cells.
filter test xs keeps the elements of xs that pass the test. On an infinite list, filter can never know that no later element passes, so it keeps reading. head (filter (> 100) rows) finishes, because 102 passes and head needs one element. With no element that passes, the same expression never finishes.
null xs asks only whether the list has a first cell, so null [1 ..] is False at once. When you need to know that a list is not empty, ask null, not length.
rows :: [Int]
rows = iterate (+ 2) 6
-- length (take 5 rows) is 5
-- length rows never finishes
-- head (filter (> 100) rows) is 102
-- head (filter (> 100) (cycle [1, 2, 3])) never finishesA function that needs the last cell never finishes on an infinite list, and filter never finishes when no later element passes.
Precisely: cells and elements
A cell and the element in it are separate pieces of work. length asks for every cell but never for the elements, so length (take 5 rows) leaves the numbers 8 to 14 as thunks. sum needs the elements as well.
Experiment
Ask for the length of a list with no end
length counts cells. take 5 gives it five, so it finishes. On rows itself, length asks for the next cell for ever, because every cell has a rest. The program gives no error and no output: it is still counting.
Why it matters Before you call length, sum, last, or reverse, check that the list has an end, or give it one with take.
Predict what line 4 asks of the list rows: its cells, its numbers, or both. Then change line 4 to print (length rows) and predict what prints.
main :: IO ()
main = do
let rows = iterate (+ 2) 6 :: [Int]
print (length (take 5 rows))
print (sum (take 5 rows))
What to look for
Line 4 prints 5. At the stop on line 5, rows shows 6 : _ (unevaluated) : _ (unevaluated) : _ (unevaluated) : _ (unevaluated) : ....: length built five cells but did not compute the numbers 8 to 14 inside them. sum needs the numbers, and the run prints 50. After the edit, no stop comes after line 3, nothing prints, and the run ends with Stopped at the 20 second execution limit.
Expected output
5
5005 / In production
What goes wrong with lazy lists in real programs?
Four mistakes with lazy lists are common in real Haskell code.
length on an infinite or a huge list. if length items > 0 never finishes on an infinite list, and on a long list it reads every cell to answer a question about one. Use null items. To ask for at least three, ask for three: length (take 3 items) == 3.
A list kept alive by a name. print (sum marks) followed by print (length marks) keeps every cell of marks in memory between the two lines, because the second line still uses the name. With ten million cells, that is a space leak. Compute both results in one walk, or do not give the list a name. Reachability and garbage collection, a later lesson, measures this memory.
filter where takeWhile was meant. filter (< 15) rows prints [6,8,10,12,14 and never closes the bracket. takeWhile (< 15) rows stops at 16. This is right only when the list is sorted so that, once one element fails, every later one fails too.
show on an infinite structure. A record that holds an infinite list and uses deriving Show prints for ever when you print or log the record. Show a part of the list instead, such as take 5.
-- never finishes: filter keeps looking after 14
filter (< 15) rows
-- stops at 16, the first row that fails
takeWhile (< 15) rowsAsk null for one cell, walk a big list once, stop a sorted infinite list with takeWhile, and show only part of an infinite list.
Experiment
Stop a sorted list where the test first fails
takeWhile stops at the first element that fails its test. filter checks every element, and on a list with no end it never reaches a last one. Only you know that rows grows, so that no row after 16 can pass.
Why it matters On a sorted list without an end, use takeWhile for a test that stays failed once it fails. filter is for finite lists.
rows grows by 2 each time. Predict what prints. Then change takeWhile to filter and predict whether the program finishes.
main :: IO ()
main = do
let rows = iterate (+ 2) 6 :: [Int]
print (takeWhile (< 15) rows)
What to look for
The run prints [6,8,10,12,14] and finishes. takeWhile reached 16, which fails (< 15), and stopped there. After the edit, the output is [6,8,10,12,14, with no closing bracket. filter has found every row below 15, but it keeps reading rows to look for another. The run ends with Stopped at the 20 second execution limit.
Expected output
[6,8,10,12,14]06 / Try it
Can you predict which cells are built?
Find which cells each line asks for before you predict.
main :: IO ()
main = do
let sizes = cycle [4, 6] :: [Int]
numbered = zip [1 ..] (take 3 sizes) :: [(Int, Int)]
total = sum sizes
print numbered
print (takeWhile (< 6) sizes)
print (null sizes)
What does the program print, and does it finish?
Reveal the reasoning
[(1,4),(2,6),(3,4)], then [4], then False, and the program finishes. take 3 sizes has three cells, so zip stops after three pairs, although [1 ..] has no end. takeWhile (< 6) stops at 6, the second element, and never reads further. null asks only whether sizes has a first cell. total = sum sizes would never finish, but no line needs total, so it is never computed.
Practice tickets
- HS-501 · The round list never appears for a repeating crochet pattern → Free
- HS-502 · Live juggling sessions show no running totals → Sign in · Pro
- HS-503 · The kite club calendar freezes on some holiday periods → Sign in · Pro
Keep exploring
Reachability and garbage collection →