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

Question

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

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

当 s 变大时将会崩溃，因为该函数不是尾递归的。我注意到 F# 的标准追加函数不会因大列表而崩溃，因此必须以不同的方式实现。所以我想知道：append 的尾递归定义是什么样的？我想出了这样的方法：

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

它有效，但看起来很奇怪。有没有更优雅的定义？

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)

使用延续（尾递归）

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)

转换起来非常简单任何非尾递归函数都优于带有延续的递归函数，但我个人更喜欢累加器，因为它具有直接的可读性。

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# 代码中的突变。

Answer 3

快速浏览一下 F# 源代码，尾部似乎在内部是可变的。一个简单的解决方案是在将第一个列表的元素连接到第二个列表之前反转第一个列表。加上反转列表，以递归方式实现尾部是微不足道的。