CODEWITHSUNDEEP
smltype-inference
DeBahroni
DeBahroni

Reputation: 13

Hint for SML type inference

I am new to SML and I am trying to practice in SML type reference.I am trying to deduct the below types:

a)fun add42 x =x+42
b)fun comp F G = let fun C x = G(F(x)) in C end
c)fun compA42 x = comp add42 x
d)val foo = compA42 add42
e)fun compCompA42 x = comp compA42 x

I think the solutions for the first four is:

a)int->int
b)(a->b)->(b->c)->a->c
c)(int->a)->int->a
d)int->int

But I am a little bit confused about the last one. Is there any hint to deduct the last type??

Thanks a lot.

Upvotes: 1

Views: 419

Answers (1)

Anton Trunov
Anton Trunov

Reputation: 15404

Let's do this manually, step-by-step:

fun compCompA42 x = comp compA42 x
  1. It's a function, so compCompA42 has type α -> β.
  2. compCompA42's return value must be of the same type as comp compA42 x, i.e. β = typeof(comp compA42 x).

  3. We already now the most general type for comp:

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

Now, we need to specialize it for the case when a -> b = typeof(compA42) and (b -> c) = α:

  1. a -> b = typeof(compA42) = (int -> d) -> int -> d. From this equation follows that a = int -> d and b = int -> d.

  2. So, α = b -> c = (int -> d) -> c and β = typeof(comp compA42 x) = a -> c = (int -> d) -> c.

  3. Finally, our most general type for compCompA42 is

    α -> β = ((int -> d) -> c) -> (int -> d) -> c.

Observe that you can always make some SML interpreter (e.g., smlnj) show you types:

- fun compCompA42 x = comp compA42 x;
val compCompA42 = fn : ((int -> 'a) -> 'b) -> (int -> 'a) -> 'b

And it's the same type we've got manually (just rename d to 'a and c to 'b).

Upvotes: 2

Related Questions