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.
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.
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.
