How does the second parameter become a list of functions?

Question

I play a little with zipWith and see the following:

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

Why does the compiler expect the next argument to the list of functions?

I tried to analyze, but could not come to a conclusion, why the next argument should be a list of functions.

How is the signature applied when I pass id to zipWith ?

Answer 1

zipWith type:

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

And id type:

 id :: d -> d 

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

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

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

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

How it works: the first list should contain a list of functions f :: b -> c , and the second list should contain a list of elements x :: b , and therefore it computes a list of elements fx :: c .

For instance:

 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 fx to these or more verbose (id f) x . Since id f f , it thus computes fx .

Thus, we can conclude that zipWith is an elementary mapping.

Answer 2

Thank you Willem Van Onsem for a great answer.

Understand the zipWith id from the eyes of the ghc type output system.

first consider the zipWith type

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

The first argument to zipWith is a function that takes a function that takes two arguments.

(a -> b -> c) can also be rewritten as a -> (b -> c)

Now consider zipWith id . id type from a -> a

we put id in the place where the function of the two arguments should go.

So a type expression would make (a -> b -> c) look like a -> (b -> c) (notification a -> (b -> c) takes one arument a and gives b -> c ie one function argument.)

But by 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))

Thus, the type input system displays a as (b -> c) , and the resulting result will [a] -> [b] -> [c] replace a with b -> c .

Replace a with (b → c).

Make (a → b → c) look like id . (a → b → c) can be made similar to id specified replacement.

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

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

So, we get the output as [b -> c] -> [b] -> [c]