CODEWITHSUNDEEP
haskell
Andriy Drozdyuk
Andriy Drozdyuk

Reputation: 61041

Function gets four arguments instead of three - why doesn't this break?

Reading "Real World Haskell", on page 95 the author provides an example:

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

My question is: Why does this code compile? foldr takes only three arguments - but here, it is passed four: step, id, xs, z.

For example, this doesn't work (because sum expects one):

sum filter odd [1,2,3]

instead I must write:

sum $ filter odd [1,2,3]

Upvotes: 9

Views: 277

Answers (3)

Dan Burton
Dan Burton

Reputation: 53665

foldr only takes 3 arguments

Wrong. All functions in Haskell take exactly 1 argument, and produce exactly 1 result.

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

See, foldr takes one argument (a -> b -> b), and produces 1 result: b -> [a] -> b. When you see this:

foldr step id xs z

Remember, it is just shorthand for this:

((((foldr step) id) xs) z)

This explains why this is nonsense:

sum filter odd [1,2,3]
(((sum filter) odd) [1,2,3])

sum :: Num a => [a] -> a takes a list as its input, but you gave it a function.

Upvotes: 9

Matt Fenwick
Matt Fenwick

Reputation: 49085

Here's the type of foldr:

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

Can we figure out how it becomes a four-argument function? Let's give it a try!

  1. we're giving it id :: d -> d as the second parameter (b), so let's substitute that into the type:

    (a -> (d -> d) -> (d -> d)) -> (d -> d) -> [a] -> (d -> d)

  2. in Haskell, a -> a -> a is the same as a -> (a -> a), which gives us (removing the last set of parentheses):

    (a -> (d -> d) -> (d -> d)) -> (d -> d) -> [a] -> d -> d

  3. let's simplify, by substituting e for (a -> (d -> d) -> (d -> d)) and f for (d -> d), to make it easier to read:

    e -> f -> [a] -> d -> d

So we can plainly see that we've constructed a four-argument function! My head hurts.

Here's a simpler example of creating an n + 1-argument function from an n-arg func:

Prelude> :t id
id :: a -> a

id is a function of one argument.

Prelude> id id id id id 5
5

But I just gave it 5 args!

Upvotes: 12

Daniel Wagner
Daniel Wagner

Reputation: 152707

It's because of how polymorphic foldr is:

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

Here, we've instantiated b to a function type, let's call it c -> c, so the type of foldr specializes to (for example)

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

Upvotes: 10

Related Questions