F # Continuation-basierte Endrekursion auf Liste

Question

ich diese ganz einfache Funktion, die einen int nimmt und fügt sie der Spitze der Liste und wird rekursiv aufgerufen mit i mit sich selbst multipliziert:

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] 

Nun, ich Ich versuche es mit einer Fortsetzung umzuschreiben, aber ich bin ein bisschen festgefahren. Hier ist, was ich bisher gefunden habe:

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] 

Alle Hinweise, was ich falsch mache?

Answer 1

Blick auf diese Fragen und die Kommentare scheint mir, dass es einige Verwirrung gibt.

Tail recursive bedeutet nicht, dass die Continuation Passing Style (CPS).

Hier ist die Funktion in 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 

Und natürlich ist es Schwanz rekursiv ist. Aber man kann es auch durch die Verwendung eines Akkumulators anstelle einer Fortsetzung Schwanz rekursive schreiben:

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 

Siehe auch die answer to this question besser CPS zu verstehen.