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

  1. Write sumList from the recursion lesson as foldr (+) 0 and check that both versions agree.
  2. Evaluate foldr (-) 0 [1, 2, 3] on paper, then in GHCi.
  3. Use foldr to write map and filter, and explain why both work on infinite lists.
  4. Replace foldl with foldl' in a sum of a million numbers and compare the runs with /usr/bin/time.
  5. Write countEven = foldr (\x n -> if even x then n + 1 else n) 0 and print its result on [1 .. 10].
  6. 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.

  1. 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.

  2. What does foldr (-) 0 [1, 2, 3] evaluate to?

    Answer

    2

    The chain is 1 - (2 - (3 - 0)), which is 1 - (2 - 3) = 2.

  3. Which fold works on an infinite list?

    Answer

    foldr

    foldr asks for elements only as the function needs them, so a function that stops early can answer.

  4. What does foldl' add to foldl?

    Answer

    It forces the accumulator at every step

    The strict fold evaluates the accumulator with seq, so the thunk chain does not grow.

  5. 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.

  6. 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.

  7. Why does foldr1 have 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.

  8. 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.

  9. 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.

  10. 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

Banner image