could have been defined through folding as head = foldr (\x r -> x) (error "head: Empty list") last = foldl (\a x -> x) (error "last: Empty list") In various languages Universality Fold is a polymorphic function. For any g having a definition g [] = v g (x:xs) = f x (g xs) then g can be expressed as g = foldr f v Also, in a lazy language with infinite lists, a fixed point combinator can be implemented via fold, proving that iterations can be reduced to folds: y f = foldr (\_ -> f) undefined (repeat undefined) See also Aggregate function Iterated binary operation Catamorphism, a generalization of fold Homomorphism Map (higher-order function) Prefix sum Recursive data type Reduction Operator Structural recursion References External links "Higher order functions — map, fold and filter" "Unit 6: The Higher-order fold Functions" "Fold in Tcl" "Constructing List Homomorphism from Left and Right Folds" "The magic foldr" Higher-order functions Recursion Programming language comparisons Articles with example Haskell code Articles with example Scheme (programming language) code Iteration in programming