Confusion about right folds in Haskell

Question

Just for Background I am a Haskell and FP Beginner, self-learning.

I was going through folds on Learn You a Haskell for great good.

In this I came across this function

map' :: (a -> b) -> [a] -> [b]  
map' f xs = foldr (\x acc -> f x : acc) [] xs

Everything is good but as far as I understood the first parameter of the lambda x matches with [] and second acc matches with xs. Right? The confusion starts with the author saying that Then, we prepend it to the accumulator, which is was []. How is the second parameter acc matching with [] which is the first argument? Doesn't make sense.

But his implementation is working while mine (with [] and xs interchanged as parameters) is giving a big error

Practice.hs:88:41:
    Couldn't match type `a' with `b'
      `a' is a rigid type variable bound by
          the type signature for map' :: (a -> b) -> [a] -> [b]
          at Practice.hs:87:9
      `b' is a rigid type variable bound by
          the type signature for map' :: (a -> b) -> [a] -> [b]
          at Practice.hs:87:9
    Expected type: [b]
      Actual type: [a]
    In the second argument of `foldr', namely `xs'
    In the expression: foldr (\ x acc -> f x : acc) xs []
    In an equation for map':
        map' f xs = foldr (\ x acc -> f x : acc) xs []
Failed, modules loaded: none.

What am I missing here? Does foldr use flip internally? Or did I just understood it all incorrectly?

Answer 1

The lambda is not applied to [] and xs. Instead it's the first argument to foldr. The second and third arguments to foldr are [] and xs respectively.

Answer 2

It helps to look at what the "symbolic" form of the fold functions looks like. If we have a list of arbitrary elements [b1, b2, b3, b4] and initial element a then:

foldr f a [b1, b2, b3, b4] = f b1 (f b2 (f b3 (f b4 a)))

Conversely the foldl would look like.

foldl f a [b1, b2, b3, b4] = f (f (f (f a b1) b2) b3) b4

This of course ignores the laziness component of the execution, but the general idea still holds.

In your function you fold a function of two arguments which pushes a an element transformed under f onto a cons list.

map' f xs = foldr (\x acc -> f x : acc) [] xs

Expanding this out where (xs=[x0,x1,...,xn]) like above yields:

map' f xs = (f x0 : (f x1 : (f x2 : ... (f xn : []))))

Where the ellipsis is just pseudocode for the all the elements in between. We see is just precisely the element wise map. Hope that helps build intuition.

Answer 3

Begin with the type of foldr, from Hoogle.

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

From this, it is apparent that the second argument of the lambda must match the second argument to foldr, i.e. acc matches [] and x is an element of xs, because the first argument of the lambda has type a, and the third argument of foldr has type [a].

Note that foldl and foldr have different signatures, and hence the arguments in the lambda are swapped.

Answer 4

Might be simplest to just look at the implementation of foldr:

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Then take a simple example like:

foldr (+) 0 [0, 1, 2, 4]

And follow exactly what happens as it recurses and generates the "spine".

Image of a foldr spine:

I'd recommend tracing what happens using pen and paper.

Answer 5

Yet another explanation, using long variable names for effect:

map :: (a -> b) -> [a] -> [b]
map f = foldr step []
    where 
      -- If you have an incomplete solution to your problem, and the first
      -- element of the input list, what is the last step you need to finish? 
      step elem incompleteSolution = f elem : incompleteSolution

The neat thing about using functions like foldr is that when you write your step function, the second argument to step will be the correct result for a smaller version of your problem.

One useful way to think of it is to imagine that foldr has already solved nearly all of your problem, but it's still missing the last step. For example, if you're trying to solve map f (x:xs), picture that foldr has already computed the solution for map f xs. Using that incomplete solution, f and x, what is the final step you need to perform to arrive at the complete solution? Well, as the code snippet illustrates, you apply f to x, and put that in front of the incomplete solution, and you're done.

The magic of foldr is that once you've figured out what to write for step, and what to use for the [] base case, then you're done. Your step function doesn't concern itself with the input list—all it can see is one input list element and an incomplete solution.