Writing foldl using foldr

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 operator

Now let us generalise from the suml example and consider the standard operator foldl that processes the elements of a list in left-to-right order by using a function f to combine values, and a value v 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 by suml = foldl (+) 0. Many other functions can be defined in a simple way using foldl. For example, the standard function reverse can redefined using foldl 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 function foldl in terms of fold:

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 of foldl, due to the fact that foldl is strict in the tail of its list argument but fold is not. There are a number of useful ‘duality theorems’ concerning fold and foldl, 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 of fold 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, the fold 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 value v of type β, the function fold 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 value v, and each cons constructor (:) within the list by the function f. In this manner, the fold 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 using fold.

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

• Haskell Wiki: Foldl as foldr
• A tutorial on the universality and expressiveness of fold, Graham Hutton, J. Functional Programming 9 (4): 355–372, July 1999.
• Malcolm, G. Algebraic data types and program transformation., PhD thesis, Groningen University.

Consider the type of foldr:

foldr :: (b -> a -> a) -> a -> [b] -> a

Whereas the type of step is something like b -> (a -> a) -> a -> a. Since step is getting passed to foldr, we can conclude that in this case the fold has a type like (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a).

Don't be confused by the different meanings of a in different signatures; it's just a type variable. Also, keep in mind that the function arrow is right associative, so a -> b -> c is the same thing as a -> (b -> c).

So, yes, the accumulator value for the foldr is a function of type a -> a, and the initial value is id. This makes some sense, because id is a function that doesn't do anything--it's the same reason you'd start with zero as the initial value when adding all the values in a list.

As for step taking three arguments, try rewriting it like this:

step :: b -> (a -> a) -> (a -> a)
step x g = \a -> g (f a x)

Does that make it easier to see what's going on? It takes an extra parameter because it's returning a function, and the two ways of writing it are equivalent. Note also the extra parameter after the foldr: (foldr step id xs) z. The part in parentheses is the fold itself, which returns a function, which is then applied to z.

^{(quickly skim through my answers [1], [2], [3], [4] to make sure you understand Haskell's syntax, higher-order functions, currying, function composition, $ operator, infix/prefix operators, sections and lambdas)}

Universal property of fold

A fold is just a codification of certain kinds of recursion. And universality property simply states that, if your recursion conforms to a certain form, it can be transformed into fold according to some formal rules. And conversely, every fold can be transformed into a recursion of that kind. Once again, some recursions can be translated into folds that give exactly the same answer, and some recursions can't, and there is an exact procedure to do that.

Basically, if your recursive function works on lists an looks like on the left, you can transform it to fold one the right, substituting f and v for what actually is there.

g []     = v              ⇒
g (x:xs) = f x (g xs)     ⇒     g = foldr f v

For example:

sum []     = 0   {- recursion becomes fold -}
sum (x:xs) = x + sum xs   ⇒     sum = foldr 0 (+)

Here v = 0 and sum (x:xs) = x + sum xs is equivalent to sum (x:xs) = (+) x (sum xs), therefore f = (+). 2 more examples

product []     = 1
product (x:xs) = x * product xs  ⇒  product = foldr 1 (*)

length []     = 0
length (x:xs) = 1 + length xs    ⇒  length = foldr (\_ a -> 1 + a) 0

Exercise:

1. Implement map, filter, reverse, concat and concatMap recursively, just like the above functions on the left side.

2. Convert these 5 functions to foldr according to a formula above, that is, substituting f and v in the fold formula on the right.

Foldl via foldr

How to write a recursive function that sums numbers up from left to right?

sum [] = 0     -- given `sum [1,2,3]` expands into `(1 + (2 + 3))`
sum (x:xs) = x + sum xs

The first recursive function that comes to find fully expands before even starts adding up, that's not what we need. One approach is to create a recursive function that has accumulator, that immediately adds up numbers on each step (read about tail recursion to learn more about recursion strategies):

suml :: [a] -> a
suml xs = suml' xs 0
  where suml' [] n = n   -- auxiliary function
        suml' (x:xs) n = suml' xs (n+x)

Alright, stop! Run this code in GHCi and make you sure you understand how it works, then carefully and thoughtfully proceed. suml can't be redefined with a fold, but suml' can be.

suml' []       = v    -- equivalent: v n = n
suml' (x:xs) n = f x (suml' xs) n

suml' [] n = n from function definition, right? And v = suml' [] from the universal property formula. Together this gives v n = n, a function that immediately returns whatever it receives: v = id. Let's calculate f:

suml' (x:xs) n = f x (suml' xs) n
-- expand suml' definition
suml' xs (n+x) = f x (suml' xs) n
-- replace `suml' xs` with `g`
g (n+x)        = f x g n

Thus, suml' = foldr (\x g n -> g (n+x)) id and, thus, suml = foldr (\x g n -> g (n+x)) id xs 0.

foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55

Now we just need to generalize, replace + by a variable function:

foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a
foldl (-) 10 [1..5] -- returns -5

Conclusion

Now read Graham Hutton's A tutorial on the universality and expressiveness of fold. Get some pen and paper, try to figure everything that he writes until you get derive most of the folds by yourself. Don't sweat if you don't understand something, you can always return later, but don't procrastinate much either.

Here's my proof that foldl can be expressed in terms of foldr, which I find pretty simple apart from the name spaghetti the step function introduces.

The proposition is that foldl f z xs is equivalent to

myfoldl f z xs = foldr step_f id xs z
        where step_f x g a = g (f a x)

The first important thing to notice here is that the right hand side of the first line is actually evaluated as

(foldr step_f id xs) z

since foldr only takes three parameters. This already hints that the foldr will calculate not a value but a curried function, which is then applied to z. There are two cases to investigate to find out whether myfoldl is foldl:

1. Base case: empty list

     myfoldl f z []
   = foldr step_f id [] z    (by definition of myfoldl)
   = id z                    (by definition of foldr)
   = z
   
     foldl f z []
   = z                       (by definition of foldl)
   

2. Non-empty list

     myfoldl f z (x:xs)
   = foldr step_f id (x:xs) z          (by definition of myfoldl)
   = step_f x (foldr step_f id xs) z   (-> apply step_f)
   = (foldr step_f id xs) (f z x)      (-> remove parentheses)
   = foldr step_f id xs (f z x)
   = myfoldl f (f z x) xs              (definition of myfoldl)
   
     foldl f z (x:xs)
   = foldl f (f z x) xs
   

Since in 2. the first and the last line have the same form in both cases, it can be used to fold the list down until xs == [], in which case 1. guarantees the same result. So by induction, myfoldl == foldl.