f# - 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 （用于累加器的常用类型）没有什么不同，除了您可以调用它并为其赋予初始值。

Answer 2

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

---

只需写下减少步骤：

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都是“如何处理将从递归调用收到的结果”。

递归案例ki，说“无论x我给出什么递归结果，s都将它放在前面，并将放大的字符串作为新的修改结果传递到链上”。

最外面的id, 只是说“按原样返回（最终）结果”。

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

添加""到字符串是一个身份操作，所以基本案例说“让连续函数链完成它们的工作，而不需要我的进一步干扰”。

注意：我一直谨慎地说“延续函数”，以避免与完全不同且更强大的野兽的一流延续混淆（虽然不确定 F# 是否有它们）。

Answer 3

在构建列表时，元素的类型与acc.

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

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