called foldr1 and foldl1, the 1 making reference to the automatic provision of an initial element, and the fact that the lists they are applied to must have at least one element. These folds use type-symmetrical binary operation: the types of both its arguments, and its result, must be the same. Richard Bird in his 2010 book proposes "a general fold function on non-empty lists" foldrn which transforms its last element, by applying an additional argument function to it, into a value of the result type before starting the folding itself, and is thus able to use type-asymmetrical binary operation like the regular foldr to produce a result of type different from the list's elements type. Implementation Linear folds Using Haskell as an example, foldl and foldr can be formulated in a few equations. foldl :: (b -> a -> b) -> b -> [a] -> b foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs If the list is empty, the result is the initial value. If not, fold the tail of the list using as new initial value the result of applying f to the old initial value and the first element. foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) If the list is empty, the result is the initial value z. If not, apply f to the first element and the result of folding the rest. Tree-like folds Lists can be folded over in a tree-like fashion, both for finite and for indefinitely defined lists: foldt f z [] = z foldt f z [x] = f x z foldt f z xs = foldt f z (pairs f xs) foldi f z [] = z foldi f z (x:xs) = f x (foldi f z (pairs f xs)) pairs f (x:y:t) = f x y : pairs f t pairs _ t = t In the case of foldi function, to avoid its runaway evaluation on indefinitely defined lists the function f must not always demand its second argument's value, at least not all of it, or not immediately (see example below). Folds for non-empty lists foldl1 f [x] = x foldl1 f (x:y:xs) = foldl1 f (f x y : xs) foldr1 f [x] =