如何实现尾递归列表追加? [英] 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# 的标准 append 函数不会因大列表而崩溃,因此必须以不同的方式实现它.所以我想知道:append 的尾递归定义是怎样的?我想出了这样的事情:
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)
将任何非尾递归函数转换为带延续的递归函数非常简单,但我个人更喜欢累加器,以提高可读性.
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屋!