*NEXT* **·**
*UP* **·**
*PREVIOUS* **·**
*CONTENTS* **·**
*INDEX*
###
Left and right folding

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.

*NEXT* **·**
*UP* **·**
*PREVIOUS* **·**
*CONTENTS* **·**
*INDEX*