CODEWITHSUNDEEP
haskell
user3203476
user3203476

Reputation: 509

foldr with 4 arguments?

I am struggling to understand why this code taken from the haskell.org exercise page typechecks (and works as a list reversal function):

myReverse :: [a] -> [a]
myReverse xs = foldr (\x fId empty -> fId (x : empty)) id xs []

My first point of confusion is that foldr accepts 3 arguments, not 4 :

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

so I am guessing that myReverse is equivalent to:

myReverse xs = foldr ((\x fId empty -> fId (x : empty)) id) xs []

but then this should not work either since in the lambda, x is a list element rather than a function ...

Upvotes: 3

Views: 1443

Answers (2)

Will Ness
Will Ness

Reputation: 71119

First of all the variables naming is atrocious. I always use r for the second argument to a foldr's reducer function, as a mnemonic for the "recursive result". "empty" is too overloaded with meaning; it is better to use some neutral name so it is easier to see what it is without any preconceived notions:

myReverse :: [a] -> [a]
myReverse xs = foldr (\x r n -> r (x : n)) id xs []

By virtue of foldr's definition,

foldr f z (x:xs)  ===  f x (foldr f z xs)

i.e.

myReverse [a,b,c,...,z]
     = foldr (\x r n -> r (x : n)) id [a,b,c,...,z] []
     = (\x r n -> r (x : n)) a (foldr (\x r n -> r (x : n)) id [b,c,...,z]) []
     = (\x r n -> r (x : n)) 
         a 
           (foldr (\x r n -> r (x : n)) id [b,c,...,z])
             []
     = let { x = a
           ; r = foldr (\x r n -> r (x : n)) id [b,c,...,z]
           ; n = []
           }
       in r (x : n)
     = foldr (\x r n -> r (x : n)) id [b,c,...,z] (a : [])
     = foldr (\x r n -> r (x : n)) id [b,c,...,z] [a]
     = ....
     = foldr (\x r n -> r (x : n)) id [c,...,z] (b : [a])
     = foldr (\x r n -> r (x : n)) id [c,...,z] [b,a]
     = ....
     = foldr (\x r n -> r (x : n)) id [] [z,...,c,b,a]
     = id [z,...,c,b,a]

I hope this illustration makes it clearer what is going on there. The extra argument is expected by the reducer function, which is pushed into action by foldr ... resulting in the operational equivalent of

     = foldl (\n x -> (x : n)) [] [a,b,c,...,z]

As it turns out, myReverse implementation is using the equivalence

foldl (flip f) n xs  ===  foldr (\x r -> r . f x) id xs n

Upvotes: 3

n. m. could be an AI
n. m. could be an AI

Reputation: 120059

Think of it this way. Every function accepts exactly one argument. It may return another function (that accepts one argument). The thing that looks like a multi-argument call

f a b c

is actually parsed as

((f a) b) c

that is, a chain of single-argument function applications. A function type

f :: a -> b -> c -> d

can be decomposed to

f :: a -> (b -> (c -> d))

i.e. a function returning a function returning a function. We usually regard it as a function of three arguments. But can it accept more than three? Yes, if d happens to be another function type.

This is exactly what happens with your fold example. The function that you pass as the first argument to foldr accepts three arguments, which is exactly the same as accepting two arguments and returning another function. Now the (simplified) type of foldr is 

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

but if you look at the first argument of it, you see it's a function of three arguments. Which is, as we have seen, exactly the same as a function that acceora two arguments and returns a function. So the b happens to be a function type. Since b is also the the return tuoe of foldr when applied to three arguments

foldr (\x fId empty -> fId (x : empty)) id

and it's a function, it can now be applied to another argument

(foldr (\x fId empty -> fId (x : empty)) id xs) []

I let you figure out what b actually is.

Upvotes: 5

Related Questions