我怎样才能实现一个尾递归列表追加？ [英] How can I implement a tail-recursive list append?

问题描述

一个简单的追加功能，像这样（在F＃）：

A simple append function like this (in F#):

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

会当s变大崩溃，因为函数不是尾递归。我注意到，F＃的标准附加功能不会大名单崩溃，所以它必须有不同的实现。所以，我在想：如何追加的尾递归定义是什么样子？我想出了这样的事情：

will crash when s becomes big, since the function is not tail recursive. I noticed that F#'s standard append function does not crash with big lists, so it must be implemented differently. So I wondered: How does a tail recursive definition of append look like? I came up with something like this:

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

这工作，但看起来相当奇怪。是否有一个更优雅的定义是什么？

which works, but looks rather odd. Is there a more elegant definition?

推荐答案

传统（不是尾递归）

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)

其pretty直截了当将任何非尾递归函数与延续，以递归的，但我个人preFER蓄电池为直接的可读性。

Its pretty straight-forward to convert any non-tail recursive function to recursive with continuations, but I personally prefer accumulators for straight-forward readability.

这篇关于我怎样才能实现一个尾递归列表追加？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！