functional-programming - 如果我们知道 k(l-1)=f(l) 适用于所有 int->int 类型的函数 f 和 int 类型的 l，我们能否确定函数“k”？

Question

假设 k 和 f 都是 int -> int 类型的函数。如果我们知道 k(l-1)=f(l) 对所有 int 类型的 l 成立，我们能确定 k 是函数 v->f(v+1) 吗？

我在进行函数式编程练习时遇到了这个问题：转换长度函数

let rec len xs = 
  match xs with 
    | [] -> 0 
    | x:xr -> 1 + len xr;;

到续传版本。我对练习的回答是

   let rec lenc xs k = 
      match xs with 
        | [] -> k 0 
        | x:xr -> lenc xr (fun v -> k(v+1))

但我不确定该(fun v -> k(v+1))部分是否可以用其他解决方案替换。要知道这一点，我们需要确定一个唯一的“k”，假设 k(l-1)=f(l) 适用于所有 int->int 类型的函数 f 和 int 类型的 l？

标签： functional-programmingf#ocamltail-recursioncontinuation-passing

Answer 1

你想要数学证明吗？

(1) k(i - 1) = f(i)

(2) j = i - 1

从（1）和（2）：

(3) k(j) = f(i)

来自（2）：

(4) i = j + 1

来自 (3) & (4)

(5) k(j) = f(j + 1)

qed

当然(fun v -> k(v+1))是你k的，里面k是f