Defining foldl in terms of foldr

Question

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)

I am currently reading a book on Haskell. And in it, it wrote its own version of the foldl function, but in terms of foldr. I do not follow.

Why are there 4 arguments for foldr?
What does the id function do?

This is mindbending for me, but the long and short of it is that there *aren't* 4 arguments for foldr. This is `(foldr step id xs) $ z` where the `foldr` builds a chain of functions applied to each other. — Adam Smith, Oct 30 '18 at 05:58
Well, it's Haskell. There's no difference between a 4-argument function and a 3-argument function that returns a 1-argument function. — Carl, Oct 30 '18 at 06:00
The id function is initial case of foldr, that is, say, when xs is [], then give me a id function. — assembly.jc, Oct 30 '18 at 07:23
same question: https://stackoverflow.com/questions/6172004/writing-foldl-using-foldr — peeyush singh, Oct 30 '18 at 08:06
Possible duplicate of [Writing foldl using foldr](https://stackoverflow.com/questions/6172004/writing-foldl-using-foldr) — Jorge Adriano Branco Aires, Nov 23 '18 at 20:10

score 3 · Answer 1 · answered Oct 30 '18 at 09:00

The thing will be become obvious when to expand the expression of foldr step id xs z:

As Adam Smith said in the comments:

foldr step id xs z = (foldr step id xs) z

Consider foldr step id xs firstly

foldr step id xs
= x1 `step` (foldr step id xs1)
= x1 `step` (x2 `step` (foldr step id xs2))
...
= x1 `step` (x2 `step` ... (xn `step` (foldr step id []))...)
= x1 `step` (x2 `step` ... (xn `step` id)...)

where

xs = (x1:xs1)
xs1 = (x2:xs2), xs = (x1:x2:xs2) 
....
xsn = (xn:[]), xs = (x1:x2...xsn) respectively

Now, apply above function with argument z, i.e.

(x1 `step` (x2 `step` ... (xn `step` id)...)) z

and let

g = (x2 `step` ... (xn `step` id)...)

gives

(x1 `step` g) z

i.e.

(step x1 g) z

and now apply the where part of foldl:

where step x g a = g (f a x)

gives

(step x1 g) z = step x1 g z = g (step z x1)

where

g (step z x1) = (x2 `step` (x3 step ... (xn `step` id)...) (step z x1)

let

g' = (x3 step ... (xn `step` id)...)

gives

(x2 `step` g') (step z x1)
= step x2 g' (step z x1)
= g' (step (step z x1) x2))
= (x3 step ... (xn `step` id)...) (step (step z x1) x2))

repeats the same steps, finally we have,

(xn `step` id) (step ....(step (step z x1) x2)....)
= step xn id (step ....(step (step z x1) x2)....)
= id (step (step ....(step (step z x1) x2)....) xn)
= (step (step ....(step (step z x1) x2)....) xn)
= foldl step z xs

and now, it is obvious that why use id function. finally, see why

foldl step z xs = (step (step ....(step (step z x1) x2)....) xn)

initial case:

foldl step z' [] = z'

recursive case:

foldl step z (x1:xs1) 
= foldl step (step z x1) xs1
= foldl step (step (step z x1) x2) xs2
...
= foldl step (step (step ....(step (step z x1) x2)....) xn) []
= (step (step ....(step (step z x1) x2)....) xn)

where

z' = (step (step ....(step (step z x1) x2)....) xn) in initial case

Just same as above.

Paul Johnson · Answer 2 · 2018-10-30T07:57:58.517

As Adam Smith says in the comments, there are only three arguments to foldr. The line in question gets parsed like this:

myFoldl f z xs = (foldr step id xs) z

There are other implicit brackets too of course, but these are the important ones.

Here is a rewrite with the type annotations, assuming scoped type variables (i.e. a and b mean the same types throughout this definition).

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs =  goFold z
   where
      goFold :: a -> a
      goFold = foldr step id xs
      step :: b -> (a -> a) -> (a -> a)  -- Last brackets are redundant
      step x g a = g (f a x)

I've moved the foldr invocation into a separate value goFold so you can see its type and how it gets applied to the z value. The step function accumulates the b values into a function of type (a -> a). Each b value processed by goFold adds an extra one of these. The "zero" for functions is of course id from the Prelude:

id :: a -> a
id x = x

The -> function operator in the types is right associative, so the last pair of brackets in the step type are redundant. But I've written it like that because it higlights the way in which step is being used; it takes a value and a function and returns a new function.

Defining foldl in terms of foldr

2 Answers2

Linked