Folds

Many recursive functions on lists follow the same pattern: combine each element with the result for the rest of the list. A fold captures that pattern once, so you don't write the recursion yourself.

foldr

foldr f z xs replaces every : in the list with f, and the final [] with z:

foldr (+) 0 [1, 2, 3]  =  1 + (2 + (3 + 0))

mySum :: [Int] -> Int
mySum = foldr (+) 0

myLength :: [a] -> Int
myLength = foldr (\_ n -> n + 1) 0

myMap :: (a -> b) -> [a] -> [b]
myMap f = foldr (\x acc -> f x : acc) []

main :: IO ()
main = do
  print (mySum [1 .. 10])
  print (myLength "fold")
  print (myMap (* 2) [1, 2, 3])
  print (foldr (\x acc -> x ++ "," ++ acc) "end" ["a", "b"])

55
4
[2,4,6]
"a,b,end"

foldl'

foldl folds from the left, carrying an accumulator:

foldl (+) 0 [1, 2, 3]  =  ((0 + 1) + 2) + 3

Always use the strict version foldl' (from Data.List) instead of plain foldl. Because of laziness, foldl builds up a huge chain of unevaluated additions before computing anything, and can run out of memory on long lists.

import Data.List (foldl')

main :: IO ()
main = do
  print (foldl' (+) 0 [1 .. 1000000])
  print (foldl' (flip (:)) [] [1, 2, 3])
  print (foldl' (\acc d -> acc * 10 + d) 0 [2, 0, 2, 6])

500000500000
[3,2,1]
2026

The last line turns a list of digits into a number, left to right. (Since GHC 9.10, foldl' is also exported by the Prelude.)

Which fold?

Scans and unfolding

scanl is a fold that keeps every intermediate result; foldr1/foldl1 use the first element as the starting value:

main :: IO ()
main = do
  print (scanl (+) 0 [1, 2, 3, 4])
  print (scanl1 max [3, 1, 4, 1, 5, 9, 2, 6])
  print (foldr1 max [3, 7, 2])
  print (takeWhile (< 100) (scanl (+) 0 [1 ..]))

[0,1,3,6,10]
[3,3,4,4,5,9,9,9]
7
[0,1,3,6,10,15,21,28,36,45,55,66,78,91]

sum, product, length, maximum, concat, and, or, any, and all are all folds under the hood.

Practice

Use a fold to write countWords :: String -> Int that counts words longer than two characters, without using length or filter.

import Data.List (foldl')

countWords :: String -> Int
countWords = foldl' step 0 . words
  where
    step n w = if length w > 2 then n + 1 else n

main :: IO ()
main = print (countWords "a fold is a very useful tool")

4