recursion - F# 列表上基于连续的尾递归

Question

我有一个非常简单的函数，它接受一个 int 并将其添加到列表的头部，并用 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]

有什么提示我做错了什么吗？

Answer 1

看看这些问题和评论，我觉得有些困惑。

尾递归并不一定意味着连续传递风格(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

当然，它是尾递归。但是您也可以使用累加器而不是延续来将其编写为尾递归:

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

另请参阅answer to this question更好地了解 CPS。