x foldr1 f (x:xs) = f x (foldr1 f xs) foldt1 f [x] = x foldt1 f (x:y:xs) = foldt1 f (f x y : pairs f xs) foldi1 f [x] = x foldi1 f (x:xs) = f x (foldi1 f (pairs f xs)) Evaluation order considerations In the presence of lazy, or non-strict evaluation, foldr will immediately return the application of f to the head of the list and the recursive case of folding over the rest of the list. Thus, if f is able to produce some part of its result without reference to the recursive case on its "right" i.e., in its second argument, and the rest of the result is never demanded, then the recursion will stop (e.g., ). This allows right folds to operate on infinite lists. By contrast, foldl will immediately call itself with new parameters until it reaches the end of the list. This tail recursion can be efficiently compiled as a loop, but can't deal with infinite lists at all — it will recurse forever in an infinite loop. Having reached the end of the list, an expression is in effect built by foldl of nested left-deepening f-applications, which is then presented to the caller to be evaluated. Were the function f to refer to its second argument first here, and be able to produce some part of its result without reference to the recursive case (here, on its left i.e., in its first argument), then the recursion would stop. This means that while foldr recurses on the right, it allows for a lazy combining function to inspect list's elements from the left; and conversely, while foldl recurses on the left, it allows for a lazy combining function to inspect list's elements from the right, if it so chooses (e.g., ). Reversing a list is also tail-recursive (it can be implemented using ). On finite lists, that means that left-fold and reverse can be composed to perform a right fold in a tail-recursive way (cf. ), with a modification to the function f so it reverses the order of its arguments (i.e., ), tail-recursively building a representation of expression that right-fold would build. The extraneous intermediate list structure can be eliminated with the continuation-passing style technique, ; similarly, ( flip is only needed in languages like Haskell with its flipped order of arguments to the combining function of foldl unlike e.g., in