The foldr function, pronounced `fold right', is also usually implemented as a curried function and has an even more sophisticated type than map. Its type is (('a * 'b) -> 'b) -> ('b -> (('a list) -> 'b)).
fun foldr f e [] = e | foldr f e (h::t) = f (h, foldr f e t);
As with map we could factor out the function argument f (and here also the value e) using let .. in .. end. Also just as with map, the foldr function preserves totality: if f is a total function, then so is foldr f. However, again foldr itself is not a total function since we can find a function f and a list l such that foldr f e l is not defined.
The utility of foldr can be seen since we may now implement the sort function with much less effort given the insert function. The following function, sort', is equivalent.
fun sort' s = foldr insert [] s;
Another use of foldr is found in the concat function of type ('a list) list -> 'a list.
fun concat s = foldr (op @) [] s;
We may define a length' function equivalent to the length function [*].
fun length' s = foldr (fn (x, y) => 1 + y) 0 s;
Now we define an alternative to foldr, called foldl, pronounced `fold left'. Its type is also (('a * 'b) -> 'b) -> ('b -> (('a list) -> 'b)).
fun foldl f e [] = e | foldl f e (h::t) = foldl f (f (h, e)) t;
If the foldl function is applied to an associative, commutative operation then the result will be the same as the result produced using foldr. However, if the operator is not commutative then the result will in general be different. For example we can define listrev as follows.
fun listrev s = foldl (op ::) [] s;
Whereas the definition using foldr gives us the list identity function.
fun listid s = foldr (op ::) [] s;
The names for foldl and foldr arise from the idea of making the operator (called f in the function definition above) associate to the right or to the left.