F # Tail-rekursiv verstehen

Question

Kürzlich lerne ich F #. Ich versuche das Problem auf verschiedene Arten zu lösen. So:

(* 

[0;1;2;3;4;5;6;7;8] -> [(0,1,2);(3,4,5);(6,7,8)] 

*) 

//head-recursive 
let rec toTriplet_v1 list= 
    match list with 
    | a::b::c::t -> (a,b,c)::(toTriplet_v1 t) 
    | _ -> [] 

//tail-recursive 
let toTriplet_v2 list= 
    let rec loop lst acc= 
     match lst with 
     | a::b::c::t -> loop t ((a,b,c)::acc) 
     | _ -> acc 
    loop list [] 

//tail-recursive(???) 
let toTriplet_v3 list= 
    let rec loop lst accfun= 
     match lst with 
     | a::b::c::t -> loop t (fun ls -> accfun ((a,b,c)::ls)) 
     | _ -> accfun [] 
    loop list (fun x -> x) 

let funs = [toTriplet_v1; toTriplet_v2; toTriplet_v3]; 
funs |> List.map (fun x -> x [0..8]) |> List.iteri (fun i x -> printfn "V%d : %A" (i+1) x) 

Ich dachte, die Ergebnisse von V2 und V3 gleich sein sollten. Aber, erhalte ich das Ergebnis unter:

V1 : [(0, 1, 2); (3, 4, 5); (6, 7, 8)] 
V2 : [(6, 7, 8); (3, 4, 5); (0, 1, 2)] 
V3 : [(0, 1, 2); (3, 4, 5); (6, 7, 8)] 

Warum die Ergebnisse von V2 und V3 unterschiedlich sind?

Answer 1

V2 verwendet Standard Variable Akkumulieren Endrekursion zu erhalten getan:

loop ([0;1;2;3;4;5;6;7;8], []) -> 
    loop ([3;4;5;6;7;8], [(0,1,2)]) -> 
    loop ([6;7;8], [(3,4,5), (0,1,2)]) -> 
     loop ([], [(6,7,8), (3,4,5), (0,1,2)]) -> 
     [(6,7,8), (3,4,5), (0,1,2)] 

V3 verwendet continuation oder in einfachem Englisch, eine Funktion Akkumulieren:

loop ([0;1;2;3;4;5;6;7;8], x->x) -> 
    loop ([3;4;5;6;7;8], x->(0;1;2)::x) -> 
    loop ([6;7;8], x->(3;4;5)::x) -> 
     loop ([], x->(6,7,8)::x) -> 
     [(6,7,8)] // x->(6,7,8)::x applies to [] 
    -> 
     [(3,4,5);(6,7,8)] // x->(3,4,5)::x applies to [(6,7,8)] 
    -> 
    [(0,1,2);(3,4,5);(6,7,8)] // x->(0,1,2)::x applies to [(3,4,5);(6,7,8)] 

Sie können sehen, der Unterschied zwischen akkumulierenden Variablen und akkumulierenden Funktionen:

Die Verwendung akkumulierender Variablen endet beim letzten Aufruf, da die akkumulierende Variable die Antwort speichert. Die Akkumulationsfunktion arbeitet jedoch nach dem letzten Aufruf noch einige backtrack. Es sollte beachtet werden, dass die Verwendung akkumulierender Funktionen tatsächlich tail rekursiv ist, da der rekursive Aufruf loop t (fun ls -> accfun ((a,b,c)::ls)) tatsächlich die letzte Anweisung dieser Funktion ist.

Btw, der Code, den Sie zur Verfügung gestellt haben, ist ein gutes Beispiel, um das Konzept Tail rekursive Funktionen zu zeigen. Eine Möglichkeit, diesen Beispielcode zu verstehen, ist die Arbeit an kleinen Fällen, wie ich in den beiden obigen Abbildungen getan habe. Nachdem Sie an einigen kleinen Fällen gearbeitet haben, werden Sie das Konzept tiefer verstehen.