Calculating types of Haskell Functions

Question

Having troubles with manually calculating types of given functions in Haskell for an exam at the weekend. I understand the basics such as: - i x = x :: t -> t - k x y = x :: t -> t1 -> t But having trouble on more complicated questions such as: - two f x = f (f x) - s x y z = x z (y z) Any explanations would be much appreciated!

Accepted Answer

In those two examples the only hints you have as to the types of the functions come from observing the application going on. In Haskell application hardly has any syntax, so I'll rewrite them a bit more obviously.

```
two f x = f(f(x))
s x y z = x(z)(y(z))
```

We'll now discover the types of these functions through gradual refinement. For instance, beginning with `two` we know that it takes in two arguments and thus must have a type which agrees with the (more general) type

```
two :: a -> b -> c
```

We also know that the `a` type variable above actually corresponds to a function because `f` is being applied to both `x` and `f(x)`.

```
two :: (a -> b) -> c -> d
```

Since `f` is applied to `x` we know that here `a` and `c` must be the same.

```
two :: (a -> b) -> a -> d
```

and since we apply `f` again to its result `f(x)` we know that the result type must be the same as the input type

```
two :: (a -> a) -> a -> b
```

And finally, the result of calling `f` is the total result of `two` so `d` must also equal `a`

```
two :: (a -> a) -> a -> a
```

This uses all of the information we have in the definition and is the most general type that is compatible with the definition of `two`.

We can do basically the same process for `s`. We know it has 3 arguments

```
s :: a -> b -> c -> d
```

We know that the first and second arguments are functions of some kind. We see the second argument applied to a single value and the first applied to two values.

```
s :: (a -> b -> c) -> (d -> e) -> f -> g
```

We also know that the first input to both functions are the same (namely, it's `z` each time). This lets us infer that `a`, `d`, and `f` are the same type

```
s :: (a -> b -> c) -> (a -> d) -> a -> e
```

We also know that the result of calling the second function is the second argument to the first function, so `b` and `d` must be the same.

```
s :: (a -> b -> c) -> (a -> b) -> a -> e
```

Finally, the result of fully applying the first function is the final result of `s` so `c` and `e` are the same

```
s :: (a -> b -> c) -> (a -> b) -> a -> c
```

While that might be a lot to digest and kind of a blur, the thing to emphasize is that the tools I've used to solve this problem are all primitive. Effectively, I introduce arrows `(->)` when I see that the type got applied to some values and thus must be a function of a certain number of arguments and I unify type variables by following the values through their expression. These are sufficient tools for inferring the types of simple functions like `two` and `s`.

Calculating types of Haskell Functions

Solution

Problem