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

另请参阅此问题的答案以了解更好的CPS.