CODEWITHSUNDEEP
recursionfunctional-programmingocamltype-inference
tfboy
tfboy

Reputation: 947

How is the type of this function inferred?

I'm scratching my head to figure out the signature of this function

let make_rec f_norec =
  let rec f x = f_norec f x in
  f

which should be

val make_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>.

Note there is a strange recursive definition. Definitely I'm missing some knowledge out there. Can anyone show me how to compute the type of the function (as the type inference system does)?

Great thanks.

Upvotes: 1

Views: 118

Answers (1)

Ingo
Ingo

Reputation: 36339

Starting with the inner ones, and working outwards:

  1. let us call the type of x a
  2. then f has type a -> b where b is the result type of f
  3. f_norec takes f and x and it must return the same type as f, hence (a->b) -> a -> b
  4. make_rec takes f_norec, and it returns f. Hence ((a->b)->a->b) -> (a->b). For syntactic reasons, the last pair of parentheses can be omitted.

Upvotes: 6

Related Questions