Folds

Can short-circuit, works on infinite lists Building structures, lazy consumers (&&, ||, :) Builds thunks (space leak risk) Rarely (prefer foldl') Evaluates the accumulator at each step Summing, counting, strict accumulation Depends on the Monoid Mapping into a Monoid and combining

Recursion schemes generalize folds (catamorphisms), unfolds (anamorphisms, unfoldr), and more. See the recursion-schemes package.

-- foldr: right fold, f x1 (f x2 (... (f xn z)))
foldr (+) 0 [1, 2, 3]          -- 1 + (2 + (3 + 0)) = 6
foldr (:) [] [1, 2, 3]         -- rebuilds the list
foldr (\x acc -> x * 2 : acc) [] [1, 2, 3]   -- map via foldr: [2,4,6]

-- foldl: left fold, f (... (f (f z x1) x2) ...) xn
foldl (-) 10 [1, 2, 3]         -- ((10 - 1) - 2) - 3 = 4
foldr (-) 10 [1, 2, 3]         -- 1 - (2 - (3 - 10)) = -8

-- foldl' (strict) is what you almost always want for left folds over big lists
import Data.List (foldl')
foldl' (+) 0 [1 .. 10000000]   -- constant space

-- Implement common functions with folds
mySum = foldr (+) 0
myLength = foldr (\_ n -> n + 1) 0
myReverse = foldl (flip (:)) []
myMap f = foldr (\x acc -> f x : acc) []
myFilter p = foldr (\x acc -> if p x then x : acc else acc) []
myAll p = foldr (\x acc -> p x && acc) True
myMaximum = foldr1 max          -- partial on []

-- foldr works on infinite lists when f is lazy in its second argument
-- foldr (\x acc -> x > 10 || acc) False [1 ..] == True
-- take 3 (foldr (\x acc -> x : acc) [] [1 ..]) == [1,2,3]