CODEWITHSUNDEEP
typesocaml
user2789945
user2789945

Reputation: 565

OCaml - Identifying the type of this function

I'm currently going through some practice problems for a midterm, but I seem to be stuck on identifying the type of this function by walking through it (not even sure where to start).

let compose f g = (fun x -> (f (g x)))

Any help/ guidance in the right direction would be greatly appreciated, thanks.

Upvotes: 0

Views: 158

Answers (2)

ivg
ivg

Reputation: 35210

the compose function has two arguments, so it should have type:

'a -> 'b -> 'c

(this 'a, 'b and 'c are type variables, just a placeholders, we will refine them in the process of derivation).

This type means: take arguments of type 'a and 'b correspondingly and return a value of type 'c.

Let's move forward, to the right hand side of the = we see a function of one argument, that means that 'c must be an arrow type also:

'a -> 'b -> ('d -> 'e)

So, the return value is a function that accepts a value of type 'd that is named x. But we can see, that g function is also applied to this value, that means, that the second parameter of our original function, that had type 'b actually must be a function, that accepts a value of type 'd also:

'a -> ('d -> 'f) -> ('d -> 'e)

Next we see, that first parameter f, that had type 'a is also a function that is applied to whatever g returns. That means, that it must be a function that accepts 'f and returns some value. But since the return value of function f is the return value of the compose function, that means that it should return 'e, so

('f -> 'e) -> ('d -> 'f) -> ('d -> 'e)

Now, lets perform a renaming, to make it look better:

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

And finally, since -> associates to the right we can remove the last two parenthesis:

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

Upvotes: 2

Syed Jafri
Syed Jafri

Reputation: 194

So the function definition is:

val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

The first set of parentheses: ('a -> 'b) says that f is a function that takes 'a and returns something of 'b

The second set of parentheses: ('c -> 'a) says that g is a function that takes something of type 'c and returns something of type 'a.

The last part 'c -> 'b says we return a function that takes something of type 'c and returns something of 'b.

To see why those types are assigned we can start by looking at this:

(g x)

So we see that g has the variable x applied to it. So g must be a function. So we can look at x assign it a type 'c. Since x:'c is applied to g, g must take 'c as a parameter and return something. Let's say it returns something of 'a. We also know that the applied expression (g x) returns something of type 'a.

Next lets look at: (f (g x)))

Since (g x):'a is applied to f. So f must also be a function. Since it is applied something of 'a we now know that it takes something of type 'a as a parameter. We can then say it returns something of type 'b. The applied expression (f (g x))) returns something of type 'b.

If my explaination confused you just let me know and I'll try to clairfy.

Upvotes: 1

Related Questions