Why does this Haskell code compile?

Question

Given:

uncurry :: (a-> b -> c) -> (a,b) -> c    
id :: a -> a

Invoking uncurry id results in a function of type: (b -> c, b) -> c

How do we get this result?

How can you use id (a -> a) as the first parameter to uncurry, which requires a (a -> b -> c) function?

Answer 1

It's easier to understand if we try and look at it from the point of making the types work out: figuring out what we need to do to id's type to get it to fit the shape required by uncurry. Since we have:

id :: a -> a

we also have:

id :: (b -> c) -> (b -> c)

This can be seen by substituting b -> c for a in the original type of id, just as you might substitute Int instead when figuring out the type of id 42. We can then drop the parentheses on the right-hand side, since (->) is right-associative:

id :: (b -> c) -> b -> c

showing that id's type fits the form a -> b -> c, where a is b -> c. In other words, we can reshape id's type to fit the required form simply by specialising the general type it already has.

Another way to understand this is to see that uncurry ($) also has the type (b -> c, b) -> c. Comparing the definitions of id and ($):

id :: a -> a
id a = a

($) :: (a -> b) -> a -> b
($) f x = f x

we can make the latter definition more point-free:

($) f = f

at which point the fact that ($) is simply a specialisation of id to a more specific type becomes clear.