[Haskell-beginners] foldl by foldr

[Matt Andrew]

Hi all,

I am working my way through 'Real World Haskell' as my first introduction to Haskell and am thoroughly enjoying both it and Haskell. I have, however, hit something of a brick wall in figuring out one of the examples used in chapter 4. The example code is flagged as 'non-trivial' to understand, but I am trying to understand each thing presented reasonably well before I move on. I was hoping someone could shed some light on the issue for me; I have done a fair amount of searching and have not found an answer, so apologies if this has come up before and I have not found it.

The offending code is:

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f zero xs = foldr step id xs zero
    where step x g a = g (f a x)

The thing I am having trouble understanding is what the 'id' function is doing in a function that expects 3 arguments and is given 4 (foldr).

Here is the breakdown of where I get stuck: My understanding of what id does as a function is that it returns the identity of the object it is passed. Playing with ghci gives me the type signature (a -> a) and as expected id returns the argument it is given unaltered. Now I believe Haskell does not allow the passing of more arguments to a function than it expects. Therefore I am driven to the conclusion that Haskell is treating the call to 'foldr' above as either:

foldr step (id xs) zero 
(i.e. the second argument is the thunk (id xs))

or:
foldr (step id) xs zero
(i.e. given that 'step' is defined above as taking 3 arguments, whereas the type signature for 'foldr' expects a function taking 2 arguments it is accepting (step id) as a partially applied function taking two arguments)

The problem is that having simulated the above scope in ghci for an identical call to 'foldr,' explicitly parenthesising the call to 'foldr' in either of the above ways throws an error. In addition to this either way of understanding the function doesn't make much sense to me: the first seems entirely redundant, the second would result in 'id' being called by 'step' in a position where it has no arguments and thus would surely result in an error.

I'm obviously missing an important part of the puzzle and would appreciate any help in understanding this code.

Appreciate you taking the time to read this,

Matt Andrew