Type Inference in Haskell for functions

Question

I am doing practice problems for Haskell and one of the problems is

test3 x y = x (x y)

for which I have to find the type.

The solution is

test3 :: (a -> a) -> a -> a

I am not understanding why the variables in the solution are all a's instead of referring to x and y as two different variables like a and b. Could someone explain that and also go through how to find the type of this problem.

Answer 1

This is quite an interesting exercise, actually. It doesn't require any Haskell-specific knowledge - it's really just basic logic.

test3 x y = x (x y)

The first thing to note is that test3 takes 2 arguments (the x and y) and produces some kind of result. So the type must be of the form

a -> b -> c

and it only remains to figure out what a, b and c are, or at least what relations exist between them.

So let's examine that result x (x y) in more detail. It tells us that x is a function which can take y as an argument. We have said that y has type b (which is a completely arbitrary name, but let's stick with it for now) - so x must be a function which takes a b and produces a result of some type. Let's call that type d for now. So we know that the type of test3 is of the form

(b -> d) -> b -> c

Finally, again from the expression x (x y), we see that x must take the x y - which we've assigned the type d - and return a result. And this result is the overall result of test3, whose type we've chosen to call c. So, in the above, x - to which we've already assigned the type b -> d, must have type d -> c. The only way b -> d can be equal to d -> c is if b, c and d are all the same type. (Because the types of functions are determine by their input type and result type.) So the overall type of test3 must be of the form

(b -> b) -> b -> b

Which is exactly what you've been told it is - up to a renaming of a to b. (The names are, as I said, arbitrary anyway - so it's not relevant.)