Comprender F#tail-recursive

tail-recursion

Question

Recientemente, estoy aprendiendo F #. Intento resolver el problema de diferentes maneras. Me gusta esto:

(*

[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)

Pensé que los resultados de V2 y V3 deberían ser los mismos. Pero, obtengo el resultado a continuación:

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)]

¿Por qué los resultados de V2 y V3 son diferentes?

Answer 1

V2 usa la variable de acumulación estándar para realizar la recursión de cola:

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 usa la continuación , o en inglés simple, una función acumulativa :

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)]

Puede ver la diferencia entre acumular variables y acumular funciones:

El uso de variables de acumulación se detiene en la última llamada ya que la variable de acumulación almacena la respuesta. Sin embargo, la función de acumulación todavía realiza algún trabajo de retroceso después de la última llamada. Debe notarse que el uso de funciones de acumulación es de hecho recursivo de cola ya que el loop t (fun ls -> accfun ((a,b,c)::ls)) llamada recursiva loop t (fun ls -> accfun ((a,b,c)::ls)) es en realidad el último enunciado de esta función.

Por cierto, el código que proporcionó es un buen ejemplo para mostrar las funciones recursivas del concepto de cola. Una forma de entender este código de muestra es trabajar en casos pequeños como lo hice en las dos ilustraciones anteriores. Después de trabajar en algunos casos pequeños, comprenderá el concepto más profundo.