基于 F# 延续的尾递归

Question

有人可以澄清对 acc "" 的需求吗？终止基于延续的尾递归函数时，如下例所示:

let rec repeat_cont i s acc = 
if i = 0 then acc ""
else repeat_cont (i-1) s (fun x -> acc(s + x))

repeat_cont 4 "xo" id
val it : string = "abababab"

如果结果是一个列表，那就是 acc [] , 和 acc 0为整数。

Answer 1

虽然其他答案提供了以连续传递风格编写函数的良好背景，但他们忽略了一个重要的观点，在我看来，它也使我更容易理解 CPS 的工作原理:

您不需要在基本情况下调用延续。 也就是说，不需要acc ""终止递归时。

我相信您理解通过一系列递归调用传递累加器并以这种方式逐渐构建数据结构的习语 - 比如说列表或树。 CPS 没有什么不同，除了您在累加器中构建的结构是一个函数。由于我们使用的是函数式语言，因此在基本情况下返回的值与其他任何值一样好。

比较以下示例:

let inline repeat_cont i s =
    let rec inner i s acc = 
        if i = 0 
            then acc
            else inner (i-1) s (fun x -> acc(s + x))
    inner i s id

let res1: string -> string = repeat_cont 4 "xo"  
res1 ""   // "xoxoxoxo"
res1 "ab" // "xoxoxoxoab"

let res2: int -> int = repeat_cont 4 1 
res2 0 // 4 
res2 5 // 9

我已经改写 repeat_cont使用内部递归函数以使其与 fsi 中的内联一起工作，否则它的代码非常相同。你会看到它的类型是 int -> 'a -> ('b -> 'b) ，即您返回一个函数作为结果。从某种意义上说，这与返回列表或 int(用于累加器的通常类型)没有什么不同，除非您可以调用它并为其赋予初始值。