foldr, foldl and foldl'
foldr
A fold replaces the constructors of a list with a function and a starting value. foldr f z [x1, x2, x3] is f x1 (f x2 (f x3 z)): the rightmost element meets z first, and the results come back to the left. The type says it: foldr :: (a -> b -> b) -> b -> [a] -> b, and the function takes the element and the folded tail.
module Main (main) where
main :: IO ()
main = do
print (foldr (+) 0 [1, 2, 3, 4] :: Int)
print (foldl (+) 0 [1, 2, 3, 4] :: Int)
print (foldl' (+) 0 [1, 2, 3, 4] :: Int)
print (foldr (:) [] [1, 2, 3] :: [Int])
print (foldr1 max [3, 9, 2] :: Int)
print (foldl (\acc x -> acc ++ [x]) [] [1, 2, 3] :: [Int])
ghc -Wall -O1 -o folds folds.hs
./folds
10
10
10
[1,2,3]
9
[1,2,3]
The fourth line is the fold that rebuilds the list itself, which is the proof that foldr is the general form of a list function: foldr (:) [] is the identity on lists. The fifth uses foldr1, which takes no starting value and therefore has no answer for the empty list; its type has no z to fall back on.
foldl
foldl f z [x1, x2, x3] is f (f (f z x1) x2) x3: the accumulator enters on the left and the elements arrive in order. For addition the result is the same as foldr, and for a non-commutative function it is not:
foldr (-) 0 [1, 2, 3] -- 1 - (2 - (3 - 0)) = 2
foldl (-) 0 [1, 2, 3] -- ((0 - 1) - 2) - 3 = -6
foldr (++) "" ["a", "b"] -- "ab"
foldl (++) "" ["a", "b"] -- "ab"
The first two lines are the ones to run in GHCi; the point is that the two folds are different functions, not two spellings of one. The reason foldl exists is the accumulator shape of the lesson on tail recursion: a loop that carries a value from left to right.
foldl' and the thunk
The accumulator of foldl is lazy, so foldl (+) 0 [1 .. n] builds a chain of n additions before it forces anything, and for a large n the chain is the memory. The third line of the program uses foldl', the strict version from Data.List, which forces the accumulator at every step with the seq of the last lesson.
foldl (+) 0 [1 .. 1000000] -- works, slowly, with a large thunk chain
foldl' (+) 0 [1 .. 1000000] -- works, in constant space
foldr (+) 0 [1 .. 1000000] -- also works: addition is lazy in its second argument
In GHC 9.10 foldl' is exported by the Prelude as well as by Data.List, which is why the program needs no import and why foldr for a function that can stop early or build a lazy structure, foldl' for a strict summary such as a sum or a count, and plain foldl only when the laziness is the point.
A fold written by hand
The recursion of the lesson on recursion is a fold with the pieces in place. Written as a general function, it makes the connection explicit and shows that there is nothing magic in the library:
module Main (main) where
myFoldr :: (a -> b -> b) -> b -> [a] -> b
myFoldr _ z [] = z
myFoldr f z (x : xs) = f x (myFoldr f z xs)
myFoldl :: (b -> a -> b) -> b -> [a] -> b
myFoldl _ z [] = z
myFoldl f z (x : xs) = myFoldl f (f z x) xs
main :: IO ()
main = do
print (myFoldr (+) 0 [1, 2, 3, 4] :: Int)
print (myFoldl (+) 0 [1, 2, 3, 4] :: Int)
print (myFoldr (:) [] [1, 2, 3] :: [Int])
print (take 3 (myFoldr (:) [] [1 ..]) :: [Int])
ghc -Wall -O1 -o hand_folds hand_folds.hs
./hand_folds
10
10
[1,2,3]
[1,2,3]
The last line is the property that separates the two folds: a hand-written foldr answers on an infinite list, because it asks for the next element only when the function needs it. A hand-written foldl on the same list would not return, since its first step demands the rest of the list.
Exercises
- Write sumList from the recursion lesson as foldr (+) 0 and check that both versions agree.
- Evaluate foldr (-) 0 [1, 2, 3] on paper, then in GHCi.
- Use foldr to write map and filter, and explain why both work on infinite lists.
- Replace foldl with foldl' in a sum of a million numbers and compare the runs with /usr/bin/time.
- Write countEven = foldr (\x n -> if even x then n + 1 else n) 0 and print its result on [1 .. 10].
- Explain why foldr1 max [] fails and what a total replacement looks like.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does
foldr (+) 0 [1, 2, 3]compute?Answer
1 + (2 + (3 + 0))
foldr associates to the right, with the starting value at the end of the chain.
-
What does
foldr (-) 0 [1, 2, 3]evaluate to?Answer
2
The chain is 1 - (2 - (3 - 0)), which is 1 - (2 - 3) = 2.
-
Which fold works on an infinite list?
Answer
foldrfoldr asks for elements only as the function needs them, so a function that stops early can answer.
-
What does
foldl'add tofoldl?Answer
It forces the accumulator at every step
The strict fold evaluates the accumulator with seq, so the thunk chain does not grow.
-
What does
foldr (:) [] [1, 2, 3]return?Answer
[1,2,3]
Replacing cons with cons and the empty list with the empty list rebuilds the same list.
-
What does this program print?
module Main (main) where main :: IO () main = print (foldr (+) 0 [1, 2, 3, 4] :: Int)Answer
10
The four elements are added to the starting value zero.
-
Why does
foldr1have no answer for the empty list?Answer
It has no starting value to return
Without a z, the empty list leaves nothing to return, so foldr1 is partial.
-
What does this program print?
module Main (main) where main :: IO () main = print (take 3 (foldr (:) [] [1 ..]) :: [Int])Answer
[1,2,3]
foldr (:) [] rebuilds the list lazily, so take 3 can take the first three elements.
-
Which fold builds
((z + x1) + x2) + x3?Answer
foldl (+) z [x1, x2, x3]foldl carries the accumulator on the left and processes the elements from left to right.
-
What does
foldr (:) []do to a list?Answer
Returns the same list
Cons and the empty list are the constructors the fold replaces, so replacing them with themselves is the identity.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev