list - 这是 F# 中尾递归的一个很好的例子吗？

Question

let  shuffley (numbers:int list) =
    let rec loop numbers acc =
        match numbers with
        | head::tail -> loop (List.rev(tail)) (head::acc)
        | [] -> List.rev(acc)
    loop numbers []
shuffley [1;2;3;4;5;6;7;8]

我正在尝试练习一些 F#，我想知道是否可以成为尾递归的一个很好的例子，或者这只是一些废话。

Answer 1

它是尾递归的，但您正在调用 List.rev输入列表的每个元素一次 -

shuffley [1;2;3;4;5;6;7;8] = // ...
  // numbers                     acc
loop [1;2;3;4;5;6;7;8]           []
loop (List.rev [2;3;4;5;6;7;8])  [1]
loop (List.rev [7;6;5;4;3;2])    [8;1]
loop (List.rev [3;4;5;6;7])      [2;8;1]
loop (List.rev [6;5;4;3])        [7;2;8;1]
loop (List.rev [4;5;6])          [3;7;2;8;1]
loop (List.rev [5;4])            [6;3;7;2;8;1]
loop (List.rev [5])              [4;6;3;7;2;8;1]
loop (List.rev [])               [5;4;6;3;7;2;8;1]
List.rev [5;4;6;3;7;2;8;1]
[1;8;2;7;3;6;4;5]

List.rev是 O(n)，因此随着输入的增长，shuffley 的过程呈指数增长。这是否使它成为 F# 中尾递归的一个很好的例子？可能不是。对于这个特定的程序，我们只需要反转输入一次 -

let shuffley l =
  let rec loop xx yy zz r =
    match xx, yy, zz with
    | _::_::xx, y::yy, z::zz -> loop xx yy zz (z::y::r)
    | _::xx   , y::_ , _     -> List.rev (y::r)
    | _                      -> List.rev r
  loop l l (List.rev l) []

printfn "%A" (shuffley [1;2;3;4;5;6;7;8])
// ...

此 loop匹配两个 xx每次迭代并产生一个非常简单的过程 -

  // xx                yy                zz                r
loop [1;2;3;4;5;6;7;8] [1;2;3;4;5;6;7;8] [8;7;6;5;4;3;2;1] []
loop [3;4;5;6;7;8]     [2;3;4;5;6;7;8]   [7;6;5;4;3;2;1]   [8;1]
loop [5;6;7;8]         [3;4;5;6;7;8]     [6;5;4;3;2;1]     [7;2;8;1]
loop [7;8]             [4;5;6;7;8]       [5;4;3;2;1]       [6;3;7;2;8;1]
loop []                [5;6;7;8]         [4;3;2;1]         [5;4;6;3;7;2;8;1]
List.rev [5;4;6;3;7;2;8;1]
[1;8;2;7;3;6;4;5]