CPS in OCaml: type doesn't check

Question

I'm working on a very simple OCaml exercise on CPS. Line 8-10 is to convert two recursive calls into one tail recursion. However, the compiler complains the type of Line 8:

File "tmp.ml", line 8, characters 9-14:

Error: This expression has type int -> int -> (int -> int) -> int but an expression was expected of type int

I understand that the compiler expects an int at line 8 because line 6 returns an int. But can someone illustrate why the type of Line 8-10 is not an int?

  4 let rec f i n k (i:int) (n:int) (k:int->int) :int =
  5     if i + n < 0 then
  6         k 1
  7     else
  8         (f i (n-1) (fun v ->
  9             f (i-1) n (fun vv->
 10                 k (v + vv))))
 11 in f 1 1 (fun x -> x)

Have you tried to leave out the type annotation? Very easy to infer the types from the operators used. — Str.

gallais gallais · Accepted Answer · 2016-03-22T15:00:28

f i n-1 is parsed as (f i n)-1 rather than the f i (n-1) you presumably expect.

Additionally,

let rec f i n k (i:int) (n:int) (k:int->int) :int

means that your function takes 6 arguments: i, n, k, i, n and k. You probably meant to write:

let rec f (i:int) (n:int) (k:int->int) :int

CPS in OCaml: type doesn't check

1 Answers