基于F#continuation的尾递归

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的工作原理:

您不需要在基本情况下调用continuation.也就是说,不需要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#是否有它们).