如何实现尾递归列表追加？
如何实现尾递归列表追加？
提问于 2010-05-19 16:33:27
一个简单的附加函数，如下所示(在F#中)：
let rec app s t =
match s with
| [] -> t
| (x::ss) -> x :: (app ss t)当s变大时会崩溃，因为函数不是尾递归的。我注意到F#的标准append函数不会在大列表中崩溃，所以它必须以不同的方式实现。所以我想知道: 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 这是可行的，但看起来相当奇怪。有没有更优雅的定义？
回答 3
Stack Overflow用户
回答已采纳
发布于 2010-05-19 16:52: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)将任何非尾递归函数转换为带有延续的递归函数是非常直接的，但我个人更喜欢累加器，因为它具有直接的可读性。
Stack Overflow用户
发布于 2010-05-19 17:44:53
除了朱丽叶发布的内容：
使用序列表达式的
在内部，序列表达式生成尾递归代码，因此这很好地工作。
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#代码中的突变。
Stack Overflow用户
发布于 2010-05-19 16:56:25
快速浏览一下F#源代码，它的尾部似乎是内部可变的。一个简单的解决方案是在将第一个列表的元素合并到第二个列表之前反转第一个列表。这与反转列表一起，对于以递归方式实现tail来说是微不足道的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2867514
复制
相似问题
实现尾递归列表操作
尾递归实现
实现尾递归
尾递归函数在列表中追加元素
如何在Scheme/Racket中使用尾递归实现追加过程？
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
社区富文本编辑器全新改版！诚邀体验～
全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验
腾讯云开发者
