如果我们知道 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?

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)

q.e.d.

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

Can we determine function "k", if we know k(l-1)=f(l) holds for all function f of type int->int and l of type int?