[Haskell-beginners] Question regarding infering the type of a function

Daniel Fischer daniel.is.fischer at web.de
Mon Sep 21 16:18:33 EDT 2009


Am Montag 21 September 2009 21:47:40 schrieb MoC:
> Hi everybody,
>
> today somebody on IRC (#haskell on Freenode) jokingly submitted the
>
> following to lambdabot:
>  > (.) (.)
>
> It turned out that (.) (.) :: (a1 -> b -> c) -> a1 -> (a -> b) -> a ->
> c. I got interested in why that is so, but unfortunately I have not been
> able to figure this out by myself yet. I know that partial application
> is used, but don't know to what it would expand to and why.
> Could someone please explain?
> (I asked on the channel, but nobody did answer so I thought I'd try my
> luck here.)

And it's not futile :)

The type of (.) is
(forall a, b, c.) (b -> c) -> (a -> b) -> a -> c

Now, to not get confused, choose different type variables for the type of the first (.) 
and the second, say the first has type

(b -> c) -> (a -> b) -> a -> c

and the second has type

(v -> w) -> (u -> v) -> u -> w === (v -> w) -> ((u -> v) -> (u -> w))

Feeding it as an argument to the first, we must unify this type with the type of the first 
(.)'s (first) argument, (b -> c), thus

b = (v -> w)
c = (u -> v) -> u -> w

and the type of (.) (.) becomes (a -> b) -> a -> c, which is

(a -> (v -> w)) -> a -> ((u -> v) -> u -> w)

by what we got for b and c.
Now remove those parentheses which aren't necessary because (->) is right associative, to 
get

(a -> v -> w) -> a -> (u -> v) -> u -> w

and rename the type variables to get exactly lambdabot's answer.
>
> Regards,
>     MoC



More information about the Beginners mailing list