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.
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.
From recursion to the standard toolkit
Recursion by hand
-- 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])(31,8)
[30,10,40,10,50,90,20,60]
[4,2,6]
11
TrueEvery 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
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)[("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:
zippairs up two lists, stopping at the shorter.zipWith fcombines them withfinstead. 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.takeWhileanddropWhilesplit a list at the first element that fails a test;spandoes both at once and returns a pair.lookupsearches a list of pairs. When the key is missing it returnsNothing, and when it is found,Justthe value. ThatMaybetype is how Haskell says "there may be no answer" without crashing; lesson 5 explains it.- The comprehension finds Pythagorean triples with
cup to 20. Three generators act like three nested loops, and the condition at the end filters. Writingb <- [1 .. c]anda <- [1 .. b]avoids listing each triangle twice. iterate f xis the infinite listx, f x, f (f x), ...;take 5makes it finite.- The last two lines import from
Data.List.sortthengroupgathers equal letters into runs, and the comprehension's patterng@(c : _)takes each run's first lettercwhile keeping the whole rungto measure.sortOn negatesorts from largest to smallest.
Folds
-- 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")(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.
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.
Seen this way, many functions are folds in disguise:
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.
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:
| Operation | Cost on a list of length n |
|---|---|
x : xs, head-style pattern match | constant |
length xs, last xs, xs !! i, elem x xs | proportional to n |
xs ++ ys | proportional to the length of xs |
reverse xs, sort xs | n, 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.MapandData.Set(packagecontainers): 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(packagetext): compact Unicode text.String, a linked list of characters, uses many bytes per character and is slow for large text. Production code usesTextfor anything bigger than a short message.- Arrays:
Data.Arrayships with GHC, and the widely usedvectorpackage from Hackage provides fast, compact arrays.
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
1. Lists, recursion and folds
Warm-upComputationalWhat does this program print?
main :: IO ()
main = print (zip [1, 2, 3] "ab")
2. Lists, recursion and folds
Warm-upComputationalWhat does this program print?
main :: IO ()
main = print [x * y | x <- [1, 2], y <- [10, 20]]
3. Lists, recursion and folds
CoreComputationalWhat does this program print?
main :: IO ()
main = print (foldr (\x acc -> x - acc) 0 [10, 4, 1])
4. Lists, recursion and folds
CoreComputationalWhat does this program print?
main :: IO ()
main = print (sum [x | x <- [1 .. 20], x `mod` 3 == 0])
5. Lists, recursion and folds
CoreComputationalWhat does this program print?
main :: IO ()
main = print (scanl (+) 100 [-30, 50, -20])
6. Lists, recursion and folds
StretchHumanWhich of these expressions finish evaluating, given that [1 ..] is infinite? Choose all that apply.
7. Lists, recursion and folds
CoreHumanA 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?
Further reading and resources
- Data.List documentation (base)Every list function in the standard library, with its complexity where it matters.
- Haskell 2010 Language Report, section 3.11: List Comprehensions
- A tutorial on the universality and expressiveness of fold · Graham Hutton · 1999A classic, readable paper showing how much can be written as a fold; published in the Journal of Functional Programming.
- The containers packageMaps, sets, sequences and graphs, for when a list is the wrong structure.