9

像这样的简单附加函数（在 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

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

4

3 回答 3

26

传统（非尾递归）

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)

将任何非尾递归函数转换为带有延续的递归函数非常简单，但我个人更喜欢累加器以提高可读性。

于 2010-05-19T16:52:26.373 回答
15

除了朱丽叶发布的内容：

使用序列表达式
在内部，序列表达式生成尾递归代码，所以这很好用。

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

于 2010-05-19T17:44:52.987 回答
1

快速浏览一下 F# 源代码，尾巴似乎在内部是可变的。一个简单的解决方案是在将第一个列表的元素放入第二个列表之前反转第一个列表。这与反转列表一起，递归地实现 tail 是微不足道的。

于 2010-05-19T16:56:24.977 回答