fibonacci cps实现

Question

我试图将不同的函数从尾递归转换为cps (延续传递样式)。

我设法完成了一个求和和阶乘函数：

和函数：

尾递归：

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版本：

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*)

阶乘(与和相同的风格)：

尾递归：

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版本：

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*)

然而，在fibonacci中，除了累加器之外还有另一个论点，这使我感到有点不安：

尾递归版本：

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尝试(不起作用)：

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;;

对这个问题的解释：

有问题的线路(根据解释性者)：

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

错误信息：

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

我只想了解如何使fibonacci的cps版本工作。

Answer 1

我想这就是你要找的-

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)

请注意，虽然上面的计算是尾递归的，但计算斐波纳契数的方法仍然非常低效。考虑一个线性迭代算法-

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

Answer 2

将尾递归版本直接转换为cps样式的方法如下

let rec fib_cps n k =
  if n <= 1 then k
  else fib_cps (n-1) (fun (prev,n) -> k (n, prev+n))
let fib n = snd @@ fib_cps n Fun.id (0,1)