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?

Worth noting that this is more commonly written `zipWith ($)`. Which works exactly the same way; the `$` operator is simply a type-narrowed version of `id`. — leftaroundabout, Aug 04 '17 at 14:48
If you've "tried to analyze", you should include the details of your attempted analysis, or potential answerers may be simply re-explaining that which you do understand, and completely missing that which you don't. — user2407038, Aug 04 '17 at 23:02

Willem Van Onsem · Accepted Answer · 2017-08-04T18:35:47.120

14

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.

edited Aug 04 '17 at 18:35

answered Aug 04 '17 at 14:33

Willem Van Onsem

443,496
30
428
555

What does the `~` mean? – softshipper Aug 04 '17 at 14:50
1

@zero_coding: it means [*type equality*](https://stackoverflow.com/a/27667708/67579). So for instance `a ~ d` means that `a` and `d` are the same types. [further reading](https://wiki.haskell.org/GHC/Type_families#Equality_constraints). – Willem Van Onsem Aug 04 '17 at 14:51
@zero_coding I have added an answer that can make you understand with out the `~`. Just though simple type inference logic. But, @Willem Van Onsem answer is really great. – Nagarjuna Pamu Aug 04 '17 at 15:32

score 5 · Answer 2 · edited Jun 20 '20 at 09:12

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]

How does the second parameter become a list of functions?

2 Answers2