F#基于Continuation的尾递归在列表上

Question

我有一个非常简单的函数，它接受一个整数并将其添加到列表的头部，然后使用i乘以自身递归调用：

let rec f i = function
    | []    -> []
    | x::xs -> (x+i)::f (i*i) xs

f 2 [1;2;3]
val it : int list = [3; 6; 19]

现在，我正试图使用续延来重写它，但是我有些困惑。以下是我迄今为止想到的：

let fC i l =
    let rec loop cont = function
        | []    -> []
        | x::xs -> cont(x+i)::loop (fun acc -> (acc*acc)) xs
    loop id l

fC 2 [1;2;3] //Expected [3;6;19]
val it : int list = [3; 16; 25]

请给我一些提示，我做错了什么吗？

- Khaine775

---

它不是尾递归，但或许可以帮助你实现：let fC i l = let rec loop cont = function | [] -> [] | x::xs -> x+cont(i)::loop (fun acc -> cont(acc*acc)) xs loop id l - DevNewb

@FoggyFinder 这不是重复的问题，那个问题问的是尾递归，而不完全是 CPS。 - Gus

@FoggyFinder 是的，但我仍然认为这个问题本身不是重复的，我认为它可以链接，因为那个问题的答案也扩展了CPS。 - Gus

https://dev59.com/hXA75IYBdhLWcg3wg5fs - FoggyFinder

@Gustavo，我明白了，我取消了我的投票。 - FoggyFinder

Answer 1

从这些问题和评论来看，我觉得有些混淆了。

尾递归并不一定意味着 continuation passing style（CPS）。

这是一个 CPS 函数：

let f' i p =
    let rec loop i p k =
        match p with
        | []    -> k []
        | x::xs -> loop (i*i) xs (fun a -> k ((x+i)::a))
    loop i p id

当然，这个函数是尾递归的。但是你也可以使用累加器而不是 continuation 的方式来编写它的尾递归版本：

let f'' i p =
    let rec loop i p acc = 
        match p with
        | []    -> acc
        | x::xs -> loop (i*i) xs ((x+i)::acc)
    loop i p [] |> List.rev

请参考这个问题的回答来更好地理解CPS。

- Gus