How does the second parameter become a list of functions?

Question

I am playing a bit with zipWith and encounter following:

Prelude Control.Applicative> :t zipWith id
zipWith id :: [b -> c] -> [b] -> [c]

Why does the compiler expect for the next argument a list of functions?

I tried to analyze, but could not conclude, why the next argument must be a list of functions.

How did the signature is getting apply, when I pass id to zipWith?

Answer 1

The type of zipWith is:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

And the type of id is:

id :: d -> d

So if we now want to derive the type of zipWith id, we push the type of id :: d -> d into the type of the first argument of zipWith:

  d -> d
~ a -> (b -> c)

So that means that: a ~ d and a ~ b -> c. So that means that the type of zipWith id is now:

   zipWith id :: [a] -> [b] -> [c]
-> zipWith id :: [b -> c] -> [b] -> [c]

How does this work: the first list has to contain a list of functions f :: b -> c, and the second list, a list of elements x :: b, and it thus calculates a list of elements f x :: c.

For example:

Prelude> zipWith id [(+1),(5/),(3*),(3-)] [1,4,2,5]
[2.0,1.25,6.0,-2.0]

since 1+1 is 2.0, 5/4 is 1.25, 3*2 is 6.0 and 3-5 is -2.0.

So zipWith id will take two elements f and x, and apply id f x on these, or more verbose (id f) x. Since id f is f, it will thus calculate f x.

We can thus conclude that zipWith is an elementwise mapping.

Answer 2

Thank you, Willem Van Onsem for the great answer.

Let's understand zipWith id from the eyes of the type inference system of ghc.

first, consider the type of zipWith

Prelude> :info zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
    -- Defined in ‘GHC.List’

First argument of zipWith is a function which accepts a function which takes two arguments.

(a -> b -> c) can also be re-written as a -> (b -> c)

now consider zipWith id. type of id is from a -> a

we have put id in a place where a two argument function must go.

So, type inference would make (a -> b -> c) look like a -> (b -> c) (notice a -> (b -> c) takes one arument a and gives b -> c i.e a single argument function.)

But, making a -> (b -> c) an identity function would be possible only if a is (b -> c).

When a is (b -> c) the function a -> b -> c becomes ((b -> c) -> (b -> c))

So, type inferencing system would infer a as (b -> c) and the resultant output would be [a] -> [b] -> [c] replacing a with b -> c.

Replace a with (b -> c).

Make (a -> b -> c) look like id. (a -> b -> c) can be made to look like id by the above replacement.

((b -> c) -> b -> c) which can also be written as ((b -> c) -> (b -> c)) which is id :: x -> x where x is (b -> c)

zipWith :: ((b -> c) -> b -> c) -> [b -> c] -> [b] -> [c]

So finally we get output as [b -> c] -> [b] -> [c]