In Real World Haskell, Chapter 4. on Functional Programming:
Write foldl with foldr:
-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
The above code confused me a lot, and somebody called dps rewrote it with a meaningful name to make it a bit clearer:
myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)
Somebody else, Jef G, then did an excellent job by providing an example and showing the underlying mechanism step by step:
myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3
But I still cannot fully understand that, here are my questions:
foldr :: (a -> b -> b) -> b -> [a] -> b
, and the first parameter is a function which need two parameters, but the step function in the myFoldl's implementation uses 3 parameters, I'm complelely confused!Some explanations are in order!
What is the id function for? What is the role of? Why should we need it here?
id
is the identity function, id x = x
, and is used as the equivalent of zero when building up a chain of functions with function composition, (.)
. You can find it defined in the Prelude.
In the above example, id function is the accumulator in the lambda function?
The accumulator is a function that is being built up via repeated function application. There's no explicit lambda, since we name the accumulator, step
. You can write it with a lambda if you want:
foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
Or as Graham Hutton would write:
5.1 The
foldl
operatorNow let us generalise from the
suml
example and consider the standard operatorfoldl
that processes the elements of a list in left-to-right order by using a functionf
to combine values, and a valuev
as the starting value:foldl :: (β → α → β) → β → ([α] → β) foldl f v [ ] = v foldl f v (x : xs) = foldl f (f v x) xs
Using this operator,
suml
can be redefined simply bysuml = foldl (+) 0
. Many other functions can be defined in a simple way usingfoldl
. For example, the standard functionreverse
can redefined usingfoldl
as follows:reverse :: [α] → [α] reverse = foldl (λxs x → x : xs) [ ]
This definition is more efficient than our original definition using fold, because it avoids the use of the inefficient append operator
(++)
for lists.A simple generalisation of the calculation in the previous section for the function
suml
shows how to redefine the functionfoldl
in terms offold
:foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v
In contrast, it is not possible to redefine
fold
in terms offoldl
, due to the fact thatfoldl
is strict in the tail of its list argument butfold
is not. There are a number of useful ‘duality theorems’ concerningfold
andfoldl
, and also some guidelines for deciding which operator is best suited to particular applications (Bird, 1998).
foldr's prototype is foldr :: (a -> b -> b) -> b -> [a] -> b
A Haskell programmer would say that the type of foldr
is (a -> b -> b) -> b -> [a] -> b
.
and the first parameter is a function which need two parameters, but the step function in the myFoldl's implementation uses 3 parameters, I'm complelely confused
This is confusing and magical! We play a trick and replace the accumulator with a function, which is in turn applied to the initial value to yield a result.
Graham Hutton explains the trick to turn foldl
into foldr
in the above article. We start by writing down a recursive definition of foldl
:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x : xs) = foldl f (f v x) xs
And then refactor it via the static argument transformation on f
:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs = g xs v
where
g [] v = v
g (x:xs) v = g xs (f v x)
Let's now rewrite g
so as to float the v
inwards:
foldl f v xs = g xs v
where
g [] = \v -> v
g (x:xs) = \v -> g xs (f v x)
Which is the same as thinking of g
as a function of one argument, that returns a function:
foldl f v xs = g xs v
where
g [] = id
g (x:xs) = \v -> g xs (f v x)
Now we have g
, a function that recursively walks a list, apply some function f
. The final value is the identity function, and each step results in a function as well.
But, we have handy already a very similar recursive function on lists, foldr
!
2 The fold operator
The
fold
operator has its origins in recursion theory (Kleene, 1952), while the use offold
as a central concept in a programming language dates back to the reduction operator of APL (Iverson, 1962), and later to the insertion operator of FP (Backus, 1978). In Haskell, thefold
operator for lists can be defined as follows:fold :: (α → β → β) → β → ([α] → β) fold f v [ ] = v fold f v (x : xs) = f x (fold f v xs)
That is, given a function
f
of typeα → β → β
and a valuev
of typeβ
, the functionfold f v
processes a list of type[α]
to give a value of typeβ
by replacing the nil constructor[]
at the end of the list by the valuev
, and each cons constructor(:)
within the list by the functionf
. In this manner, thefold
operator encapsulates a simple pattern of recursion for processing lists, in which the two constructors for lists are simply replaced by other values and functions. A number of familiar functions on lists have a simple definition usingfold
.
This looks like a very similar recursive scheme to our g
function. Now the trick: using all the available magic at hand (aka Bird, Meertens and Malcolm) we apply a special rule, the universal property of fold, which is an equivalence between two definitions for a function g
that processes lists, stated as:
g [] = v g (x:xs) = f x (g xs)
if and only if
g = fold f v
So, the universal property of folds states that:
g = foldr k v
where g
must be equivalent to the two equations, for some k
and v
:
g [] = v
g (x:xs) = k x (g xs)
From our earlier foldl designs, we know v == id
. For the second equation though, we need
to calculate the definition of k
:
g (x:xs) = k x (g xs)
<=> g (x:xs) v = k x (g xs) v -- accumulator of functions
<=> g xs (f v x) = k x (g xs) v -- definition of foldl
<= g' (f v x) = k x g' v -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x)) -- expand k. recursion captured in g'
Which, substituting our calculated definitions of k
and v
yields a
definition of foldl as:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs =
foldr
(\x g -> (\a -> g (f v x)))
id
xs
v
The recursive g
is replaced with the foldr combinator, and the accumulator becomes a function built via a chain of compositions of f
at each element of the list, in reverse order (so we fold left instead of right).
This is definitely somewhat advanced, so to deeply understand this transformation, the universal property of folds, that makes the transformation possible, I recommend Hutton's tutorial, linked below.
References