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

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 

哪个有效,但看起来很奇怪.是否有更优雅的定义？

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

除了朱丽叶发布的内容:

使用序列表达式在
内部,序列表达式生成尾递归代码,因此这很好用.

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