Понимание хвостовой рекурсии F # - PullRequest
Новая
       21

Понимание хвостовой рекурсии F #

8 голосов
/ 01 июня 2010

Недавно я изучаю F #. Я пытаюсь решить проблему по-разному. Как это: 

(*

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

Я думал, что результаты V2 и V3 должны быть одинаковыми. Но я получаю результат ниже: 

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

Почему результаты V2 и V3 отличаются?

1 Ответ

11 голосов
/ 01 июня 2010

V2 использует стандартную аккумулирующую переменную для выполнения хвостовой рекурсии: 

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 использует продолжение , или простым языком, функция накопления : 

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

Вы можете увидеть разницу между накапливающимися переменными и накапливающими функциями:

Использование накапливающихся переменных прекращается при последнем вызове, так как накапливающая переменная хранит ответ. Однако функция накопления по-прежнему выполняет некоторую возврат после последнего вызова. Следует отметить, что использование аккумулирующих функций действительно является хвостовой рекурсией, поскольку рекурсивный вызов loop t (fun ls -> accfun ((a,b,c)::ls)) на самом деле является последним оператором этой функции.

Кстати, код, который вы предоставили, является хорошим примером для демонстрации концепции рекурсивных функций хвоста. Один из способов понять этот пример кода - это работать с небольшими делами , как я делал на двух приведенных выше иллюстрациях. Поработав над некоторыми мелкими делами, вы поймете концепцию глубже.

...