Skip to content
LumenaryAcademy
Foundations 55 min

Lists, recursion and folds

The list is Haskell's everyday collection; recursion processes it, and higher-order functions and folds capture the recursion once and for all.

Code tested · 3AI-draftedAwaiting review by a computer scientist
MotivationH

Where did the loops go?

Haskell has no for and no while. That sounds alarming until you notice what loops are usually for: doing something to every element of a collection, keeping some of the elements, combining them into one result, or walking two collections side by side. In Haskell each of those jobs has a name (map, filter, a fold, zip), and once you know a dozen such names you will find you rarely miss loops at all.

The collection those functions work on first is the list, and in this lesson you will see lists from three angles: how they are built, how recursion processes them, and how a few higher-order functions capture that recursion so you don't have to write it again.

DefinitionsH

Lists, precisely

Definition— List

A list of type [a] is either empty, written [], or an element of type a in front of another list of type [a], written x : xs and pronounced "x cons xs". That is all a list is. The bracket notation is shorthand: [7, 8, 9] means 7 : (8 : (9 : [])), and : associates to the right, so the parentheses can be dropped: 7 : 8 : 9 : [].

Because a list is built from the front, getting the first element or adding a new one at the front takes constant time, while reaching the end means walking the whole list. Keep that in mind; it explains most of the performance advice at the end of the lesson.

Definition— Range and comprehension

[1 .. 5] is [1, 2, 3, 4, 5]; [2, 4 .. 10] steps by two; ['a' .. 'e'] works for characters; [1 ..] never ends. A list comprehension [expr | x <- xs, condition] builds the list of expr for every x drawn from xs that satisfies the condition. Several generators can be combined, and the later ones vary fastest, like nested loops.

Definition— Higher-order function

A function that takes a function as an argument, or returns one, is higher-order. map :: (a -> b) -> [a] -> [b] applies a function to every element; filter :: (a -> Bool) -> [a] -> [a] keeps the elements satisfying a test.

Definition— Fold

A fold reduces a list to a single value by combining its elements with a function, starting from an initial value. foldr f z combines from the right, f x1 (f x2 (... (f xn z))); the strict left fold foldl' f z combines from the left, f (... (f (f z x1) x2) ...) xn, keeping a running total.

Worked examplesH

From recursion to the standard toolkit

Recursion by hand

haskell
-- Four recursive functions with the same skeleton:
-- an answer for the empty list, and a way to combine the first element
-- with the answer for the rest.
mySum :: [Int] -> Int
mySum [] = 0
mySum (x : xs) = x + mySum xs

myLength :: [a] -> Int
myLength [] = 0
myLength (_ : xs) = 1 + myLength xs

myMap :: (a -> b) -> [a] -> [b]
myMap _ [] = []
myMap f (x : xs) = f x : myMap f xs

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter _ [] = []
myFilter keep (x : xs)
  | keep x = x : myFilter keep xs
  | otherwise = myFilter keep xs

main :: IO ()
main = do
  let xs = [3, 1, 4, 1, 5, 9, 2, 6]
  print (mySum xs, myLength xs)
  print (myMap (* 10) xs)
  print (myFilter even xs)
  print (myLength "Ouagadougou")
  print (1 : 2 : 3 : [] == [1, 2, 3])
text
(31,8)
[30,10,40,10,50,90,20,60]
[4,2,6]
11
True

Every one of these functions has two equations: one for [], one for x : xs. The second does something with x and makes a recursive call on xs. That shape is called structural recursion: the function's structure follows the list's structure, and it is guaranteed to finish on any finite list because each call gets a shorter one.

Look at the types, too. myLength :: [a] -> Int works on lists of anything, including strings, since it never looks at the elements. myMap takes a function from a to b and turns a list of as into a list of bs. These are exactly the standard length, map and filter; real code uses the standard ones.

The standard toolkit

haskell
import Data.List (group, sort, sortOn)

main :: IO ()
main = do
  let temps = [21, 24, 19, 30, 28, 17, 25] :: [Int]
      days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
  print (zip days temps)
  print (zipWith (-) (drop 1 temps) temps) -- change from one day to the next
  print (takeWhile (/= "Thu") days, dropWhile (/= "Thu") days)
  print (span (< 25) temps)
  print (lookup "Fri" (zip days temps), lookup "Funday" (zip days temps))
  print (maximum temps, minimum temps, sum temps `div` length temps)
  print [(a, b, c) | c <- [1 .. 20], b <- [1 .. c], a <- [1 .. b], a * a + b * b == c * c]
  print (take 5 (iterate (* 3) 1), replicate 3 'z', concatMap show [1, 2, 3])
  print [(c, length g) | g@(c : _) <- group (sort "mississippi")]
  print (sortOn negate temps)
text
[("Mon",21),("Tue",24),("Wed",19),("Thu",30),("Fri",28),("Sat",17),("Sun",25)]
[3,-5,11,-2,-11,8]
(["Mon","Tue","Wed"],["Thu","Fri","Sat","Sun"])
([21,24,19],[30,28,17,25])
(Just 28,Nothing)
(30,17,23)
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20)]
([1,3,9,27,81],"zzz","123")
[('i',4),('m',1),('p',2),('s',4)]
[30,28,25,24,21,19,17]

A tour, line by line:

  • zip pairs up two lists, stopping at the shorter. zipWith f combines them with f instead. Zipping a list with its own tail (drop 1 temps) is the idiomatic way to look at neighbouring pairs, here the change from each day to the next.
  • takeWhile and dropWhile split a list at the first element that fails a test; span does both at once and returns a pair.
  • lookup searches a list of pairs. When the key is missing it returns Nothing, and when it is found, Just the value. That Maybe type is how Haskell says "there may be no answer" without crashing; lesson 5 explains it.
  • The comprehension finds Pythagorean triples with c up to 20. Three generators act like three nested loops, and the condition at the end filters. Writing b <- [1 .. c] and a <- [1 .. b] avoids listing each triangle twice.
  • iterate f x is the infinite list x, f x, f (f x), ...; take 5 makes it finite.
  • The last two lines import from Data.List. sort then group gathers equal letters into runs, and the comprehension's pattern g@(c : _) takes each run's first letter c while keeping the whole run g to measure. sortOn negate sorts from largest to smallest.

Folds

haskell
-- Folds capture the recursion pattern once and for all.
main :: IO ()
main = do
  let xs = [1 .. 10] :: [Int]
  print (foldr (+) 0 xs, foldr (*) 1 xs)
  print (foldr (\x acc -> show x ++ "," ++ acc) "end" [1, 2, 3])
  print (foldl (\acc x -> "(" ++ acc ++ "-" ++ show x ++ ")") "0" [1, 2, 3])
  print (foldl' (+) 0 [1 .. 1000000 :: Int])
  -- foldr can stop early on an infinite list when the function ignores acc:
  print (foldr (\x acc -> x > 100 || acc) False [1 ..])
  -- A running balance: scanl keeps every intermediate result.
  let movements = [500, -120, -75, 1000, -430] :: [Int]
  print (scanl (+) 0 movements)
  -- Reversing with a left fold: flip (:) puts each element in front.
  print (foldl (flip (:)) [] "stressed")
text
(55,3628800)
"1,2,3,end"
"(((0-1)-2)-3)"
500000500000
True
[0,500,380,305,1305,875]
"desserts"

The second and third lines make the direction of each fold visible. foldr combines from the right: it computes "1," ++ ("2," ++ ("3," ++ "end")), so the initial value ends up at the far right. foldl starts from the initial value on the left, and the parentheses it builds show the nesting: (((0-1)-2)-3). For addition the direction does not change the answer, but for subtraction, string building or anything else that is not associative, it does.

foldl' (with an apostrophe, pronounced "fold-L-prime") is the left fold that keeps its running total fully evaluated at every step. Use it whenever you reduce a long list to a number: a sum, a count, a maximum. In GHC 9.10 and later it is part of the Prelude; with older compilers write import Data.List (foldl') at the top of the file.

The fifth line is remarkable: a fold over an infinite list finishes. foldr calls the function as f 1 (foldr f z [2 ..]), and because Haskell is lazy, that second argument is not computed unless f looks at it. || returns True as soon as its left side is true, so when x reaches 101 the rest of the list is never touched. This is why foldr is the right fold for building lists and for searches that may stop early, and why the standard functions any, all, and, or, elem, map and concat all work on infinite lists.

scanl is a fold that keeps every intermediate result, ideal for running totals such as an account balance. And foldl (flip (:)) [] reverses a list; it is exactly how the Haskell 2010 Report defines the standard reverse.

IntuitionH

What foldr really does

There is a beautifully simple way to see foldr. A list is built from : and []. foldr f z replaces every : with f and the final [] with z, leaving the structure otherwise untouched.

:1:2:3[]+1+2+30foldr (+) 0
foldr (+) 0 rewrites the list 1 : (2 : (3 : [])) into 1 + (2 + (3 + 0)) by swapping each constructor for the function and the initial value.

Seen this way, many functions are folds in disguise:

haskell
sum      = foldr (+) 0
product  = foldr (*) 1
and      = foldr (&&) True
map f    = foldr (\x acc -> f x : acc) []
filter p = foldr (\x acc -> if p x then x : acc else acc) []
xs ++ ys = foldr (:) ys xs

(The real definitions in the standard library differ in details, for speed, but compute the same results.) The last line is a small gem: to append ys to xs, replace the final [] of xs by ys and leave every : alone.

foldl and foldl' see the list the other way, as a sequence of updates to an accumulator, which is how you would write the loop in Python: acc = z, then acc = f(acc, x) for each x. When you think "running total", think foldl'. When you think "rebuild the structure" or "stop early", think foldr.

ExplanationH

Lists in professional code

Lists are perfect for what they are: sequences that you produce and consume from the front, often lazily, often only once. Much of a Haskell program is lists flowing through map, filter and folds, and GHC is very good at fusion, optimising chains like sum (map f (filter p xs)) into a single loop that never builds the intermediate lists.

They are the wrong tool for some jobs, and knowing the costs keeps you out of trouble:

OperationCost on a list of length n
x : xs, head-style pattern matchconstant
length xs, last xs, xs !! i, elem x xsproportional to n
xs ++ ysproportional to the length of xs
reverse xs, sort xsn, and n log n

So: do not call length in a loop condition, do not index lists with !! in a loop, and do not build a long list by repeatedly appending at the end (acc ++ [x] inside a fold costs time proportional to n² overall; build it with : and reverse once at the end, or use foldr).

When you need something else, the libraries that ship with GHC have it:

  • Data.Map and Data.Set (package containers): sorted maps and sets with logarithmic lookup, insertion and deletion. The usual choice for a dictionary.
  • Data.Sequence: a sequence with fast access at both ends and fast indexing.
  • Data.Text (package text): compact Unicode text. String, a linked list of characters, uses many bytes per character and is slow for large text. Production code uses Text for anything bigger than a short message.
  • Arrays: Data.Array ships with GHC, and the widely used vector package from Hackage provides fast, compact arrays.
Common misconceptionsH

Common misconceptions

Misconception

"foldl is the efficient fold because it is like a loop." Plain foldl is lazy in its accumulator: on a long list it can build up millions of unevaluated additions before doing any of them, using far more memory than needed. GHC's optimiser often rescues compiled code, but you should not rely on it. Use foldl' for strict accumulation; lesson 8 explains exactly what goes wrong.

Misconception

"length is free, like len in Python." A Haskell list does not store its length; length walks the whole list. On an infinite list it never returns.

Misconception

"Ranges of Doubles stop at the limit, like ranges of integers." For fractional types, a range runs until it passes the limit by more than half a step, so in GHCi [1.0 .. 3.5] :: [Double] is [1.0,2.0,3.0,4.0] and [1, 3 .. 10] :: [Double] ends with 11.0. Rounding errors also creep in: [0.1, 0.2 .. 0.5] contains 0.30000000000000004. For fractional values, generate integers and convert: [fromIntegral i / 10 | i <- [1 .. 5]].

Misconception

"List comprehensions are a separate feature from map and filter." They are the same thing in a different notation: [f x | x <- xs, p x] is map f (filter p xs). Use whichever reads better. Many Haskell programmers prefer comprehensions for several generators and map/filter for one.

Misconception

"Strings in Haskell are slow, so Haskell is slow at text." String is slow; Haskell is not. With Data.Text and Data.ByteString, text processing in Haskell is competitive with other compiled languages. String survives in the Prelude for simplicity and history.

Exercises

Exercises

1. Lists, recursion and folds

Warm-upComputational

What does this program print?

main :: IO ()
main = print (zip [1, 2, 3] "ab")

2. Lists, recursion and folds

Warm-upComputational

What does this program print?

main :: IO ()
main = print [x * y | x <- [1, 2], y <- [10, 20]]

3. Lists, recursion and folds

CoreComputational

What does this program print?

main :: IO ()
main = print (foldr (\x acc -> x - acc) 0 [10, 4, 1])

4. Lists, recursion and folds

CoreComputational

What does this program print?

main :: IO ()
main = print (sum [x | x <- [1 .. 20], x `mod` 3 == 0])

5. Lists, recursion and folds

CoreComputational

What does this program print?

main :: IO ()
main = print (scanl (+) 100 [-30, 50, -20])

6. Lists, recursion and folds

StretchHuman

Which of these expressions finish evaluating, given that [1 ..] is infinite? Choose all that apply.

Choose all that apply

7. Lists, recursion and folds

CoreHuman

A colleague builds a list of 100,000 results with foldl' (\acc x -> acc ++ [f x]) [] xs and finds it very slow. Why, and what is the usual fix?

Choose one

Further reading and resources