Confusion about right folds in Haskell

1
votes

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?

5
haskelllambdafold
Hmm, I'm not sure what you mean by "matches with". Eventually, in your example, the given function gets called with [] in it's second argument. - David Young
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. - Tom Ellis
@DavidYoung What I meant was that it looked to me that the first parameter(to lambda) corresponded to first argument(The []) like in imperative programming. I had forgotten that the lambda was also an argument to foldr alongwith the other 2 arguments. And it was upto foldr to apply it to its 2 other arguments. Just like @TomEllis said. - Aseem Bansal
@TomEllis You should make that comment into an answer. That was the main thing that I had overlooked which led to this question. - Aseem Bansal
OK, I made it an answer. - Tom Ellis

5 Answers

4
votes

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.

3
votes

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.

2
votes

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.

2
votes

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:

enter image description here

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

1
votes

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.