fibonacci cps implementation

Question

I'm trying to convert different function from tail recursive to cps (continuation passing style).

I managed to do a sum and factorial function:

Sum function:

Tail recursive:

let sum n =
  let rec subSum n acc =
    match n with
    |0 -> acc
    |_ -> subSum (n-1) (n+acc)
  in subSum n 0;;

Printf.printf "%u\n" (sum 5);; (*returns 15*)

cps version:

let sum2 n =
  let rec sum_cps n acc =
    match n with
    |0 -> acc 0
    |_ -> sum_cps (n-1) (fun r -> acc (n+r))
  in sum_cps n (fun n -> n);;

Printf.printf "%u\n" (sum2 5);; (*returns 15*)

factorial (same style as sum):

tail recursive:

let fact n =
  let rec subFact n acc =
    match n with
    |0 -> acc
    |1 -> acc
    |_ -> subFact (n-1) (n*acc)
  in subFact n 1;;

Printf.printf "%u\n" (fact 6);; (*returns 720*)

cps version:

let fact2 n =
  let rec fact_cps n acc =
    match n with
    |0 -> acc 1
    |1 -> acc 1
    |_ -> fact_cps (n-1) (fun r -> acc (n*r))
  in fact_cps n (fun n -> n);;

Printf.printf "%u\n" (fact2 6);; (*returns 720*)

However, in fibonacci, there is another argument in addition to the accumulator and that disturbs me a little bit:

tail recursive version:

let fibo n =
  let rec fibon n acc prev =
    match n with
    |0 -> acc
    |_ -> fibon (n-1) (prev+acc) acc
  in fibon n 0 1;;

Printf.printf "%u\n" (fibo 6);; (*returns 8*)

cps attempt (not working):

let fibo n =
  let rec fibo_cps n acc prev =
    match n with
    |0 -> 0
    |_ -> fibo_cps (n-1) (fun r -> acc (prev+r)) acc
  in fibo_cps n (fun n -> n) 1;;

explainations of the problem:

problematic line (according to the interpretor):

|_ -> fibo_cps (n-1) (fun r -> acc (prev+r)) acc

error message:

Line 5, characters 49-52: Error: This expression has type int -> 'a but an expression was expected of type int

I would just like to understand how to make a working cps version of fibonacci.

Answer 1

I think this is what you're looking for -

let fibo n =
  let rec fibo_cps n acc =
    match n with
    |0 -> acc 0
    |1 -> acc 1
    |_ -> fibo_cps (n-1) (fun x -> fibo_cps (n-2) (fun y -> acc (x+y)))
  in fibo_cps n (fun x -> x)

Please note that while the computation above is tail-recursive, it's still a very inefficient way to compute fibonacci numbers. Consider a linear iterative algorithm -

let fibo2 n =
  let rec aux n a b =
    match n with
    |0 -> a 
    |_ -> aux (n-1) b (a+b)
  in aux n 0 1