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

构建列表时，元素的类型与 acc 的结果相同。

要终止递归，您需要一个基本情况，因此您使用已知值调用 acc 以生成具有正确类型的内容。

鉴于您的示例 acc = id，您可以将 acc "" 替换为 ""

Answer 2

编辑： 这被称为 continuation-passing style。每个递归调用都会构建其延续函数并将其传递给下一个递归调用，以供该调用选择使用（取决于它是否是基本情况）。

只需记下还原步骤：

repeat_cont 4 "xo" id
repeat_cont 3 "xo" k1     where   k1 x = id ("xo" + x)
repeat_cont 2 "xo" k2     where   k2 x = k1 ("xo" + x)
repeat_cont 1 "xo" k3     where   k3 x = k2 ("xo" + x)
repeat_cont 0 "xo" k4     where   k4 x = k3 ("xo" + x)
k4 ""
k3 ("xo" + "")
k2 ("xo" + ("xo" + ""))
k1 ("xo" + ("xo" + ("xo" + "")))
id ("xo" + ("xo" + ("xo" + ("xo" + ""))))
"xoxoxoxo"

每个延续函数 ki 是 "what to do with the result that will be received from the recursive call"。

递归案例 ki，比如 "whatever recursive result x I'm given, prepend s to it and pass the enlarged string up the chain as the new, modified result"。

最外面的id，就是"return the (final) result as is"。

当达到 0 的基本情况时，k4 延续函数已构建并准备好接收其参数，以完成其工作。它会将 "xo" 字符串添加到它的参数中，并将结果沿着延续函数链向上传递到 k3。该参数将在 "xo" + x 中使用，因此它必须是一个字符串。

将 "" 添加到字符串是恒等操作，因此基本情况为 "just let the chain of continuation functions do their job, without further interference from me".

注意：我总是谨慎地说 "continuation function"，以避免与 first-class continuations 混淆，后者是完全不同且更强大的野兽（但不确定 F# 是否有它们） .

Answer 3

虽然其他答案提供了以延续传递风格编写函数的良好背景，但他们遗漏了一个重要的点，在我看来这也使理解 CPS 的工作原理变得更容易：

基本情况下不需要调用continuation即终止递归时不需要acc ""

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

比较下面的例子：

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)，即你得到一个函数作为结果。从某种意义上说，这与 returning 一个列表或一个 int（用于累加器的常用类型）没有什么不同，除了你可以调用它给它初始值。

F# 基于延续的尾递归

F# continuation-based tail recursion

f#

tail-recursion

continuation-passing