如何实现尾递归的列表追加？

Question

像这样的一个简单的追加函数（在F#中）：

let rec app s t =
   match s with
      | [] -> t
      | (x::ss) -> x :: (app ss t)

如果s变得很大，该函数将崩溃，因为它不是尾递归的。我注意到F#的标准附加函数在处理大列表时不会崩溃，所以它必须是以不同的方式实现的。因此，我想知道：尾递归定义的附加函数是什么样子的？我想到了以下代码：

let rec comb s t =
   match s with
      | [] -> t
      | (x::ss) -> comb ss (x::t)
let app2 s t = comb (List.rev s) t 

这个方法虽然可行，但看起来有些奇怪。是否有更优雅的定义？

- martingw

Answer 1

传统的（非尾递归）

let rec append a b =
    match a, b with
    | [], ys -> ys
    | x::xs, ys -> x::append xs ys

使用累加器（尾递归）

let append2 a b =
    let rec loop acc = function
        | [] -> acc
        | x::xs -> loop (x::acc) xs
    loop b (List.rev a)

使用 continuation (尾递归)

let append3 a b =
    let rec append = function
        | cont, [], ys -> cont ys
        | cont, x::xs, ys -> append ((fun acc -> cont (x::acc)), xs, ys)
    append(id, a, b)

将任何非尾递归函数转换为带有continuations的递归函数相当直接，但是我个人更喜欢累加器来提高代码的可读性。

- Juliet

---

在第一个例子中，如果所有模式中的b都是相同的，那么进行模式匹配的目的是什么？你可以直接使用b。 - Rubys

你确定它能正常工作吗？我得到了

append2 [1;2] [3;4];; val it : int list = [2; 3; 4]

和

append3 [1;2] [3;4];; val it : int list = [1; 3; 4]

虽然我没有看到错误，但是对我来说append2看起来没问题。 - martingw

非常奇怪。你的代码完全没问题，在fsc上运行正常。但在fsi中无法运行。这不是我在mono上遇到的第一个问题了。 - martingw

append3比append2更高效吗？ - day

有没有办法实现尾递归、累加器版本而不翻转第一个列表？ - Derek Mahar

Answer 2

除了Juliet发布的内容之外：

使用序列表达式
内部，序列表达式会生成尾递归代码，所以这样做完全没有问题。

let append xs ys = 
  [ yield! xs
    yield! ys ]

使用可变的 .NET 类型
David提到过，F#列表可以被改变，但这只限于F# 核心库（而且这个特性不能被用户使用，因为它会破坏函数式概念）。您可以使用可变的 .NET 数据类型来实现基于突变的版本：

let append (xs:'a[]) (ys:'a[]) = 
  let ra = new ResizeArray<_>(xs)
  for y in ys do ra.Add(y)
  ra |> List.ofSeq

在某些情况下，这可能有用，但我通常会避免在F＃代码中进行变异。

- Tomas Petricek

Answer 3

从快速浏览 F# 源代码来看，似乎尾部是内部可变的。一个简单的解决方案是在将第一个列表的元素连接到第二个列表之前先反转它。这个方法以及反转列表都可以很容易地实现尾递归。

- Daniel