foldr

foldr is a higher-order function used to reduce a list from the right side using a binary function and a base value. In Haskell its type is foldr :: (a -> b -> b) -> b -> [a] -> b. It takes a function f, a base value z, and a list xs, and computes foldr f z xs by applying f to each element and the result of folding the tail: foldr f z [] = z; foldr f z (x:xs) = f x (foldr f z xs).

Conceptually, foldr performs a right-associative fold. For a list [x1, x2, ..., xn], foldr f z [x1, x2, ..., xn] equals f x1 (f x2 (... (f xn z))). This makes foldr naturally suited to constructing or transforming lists and to expressing operations in terms of the list’s structure.

Common uses include defining alternative list operations. For example, sum xs can be defined as foldr (+) 0 xs, and product as foldr (*) 1 xs. A map can be implemented with foldr as map f = foldr (\x acc -> f x : acc) []. A filter can be expressed as filter p = foldr (\x acc -> if p x then x : acc else acc) [].

Laziness is a defining trait of foldr in a non-strict language like Haskell. It can work with infinite lists when the combining function can produce a result without traversing the entire tail, such as using (||) for boolean OR. However, foldr is not strictly evaluating in the accumulator, and for strict accumulation over large lists, a strict fold such as foldl' from Data.List may be preferred to avoid building large thunks.