将元素添加到列表末尾的最简单方法是什么？

Question

由于:: : 'a -> 'a list -> 'a list用于向列表的开头添加元素,有人可以告诉我是否有一个函数将元素添加到列表的末尾？如果没有,我想这List.rev (element::(List.rev list))是最简单的方法吗？

谢谢!

Answer 1

没有标准功能的原因是在列表末尾追加是反模式(又称"snoc列表"或Schlemiel the Painter算法).在列表末尾添加元素需要列表的完整副本.在列表的前面添加元素需要分配单个单元格 - 新列表的尾部可以指向旧列表.

也就是说,最直接的方法是

let append_item lst a = lst @ [a]

Answer 2

list@[element]应该管用.@加入列表.

Answer 3

鉴于此操作是线性的,您不应在代码的"热门"部分使用它,因为性能很重要.在寒冷的部分,使用list @ [element]建议Adi.在一个热门部分,重写您的算法,这样您就不需要这样做了.

执行此操作的典型方法是在处理期间以相反顺序累积结果,然后在返回结果之前反转整个累积列表.如果您有N个处理步骤(每个都向列表中添加一个元素),那么您可以分摊N个元素的反向线性成本,因此您保持线性算法而不是二次算法.

在某些情况下,另一种有效的技术是以相反的顺序处理您的元素,以便累积的结果在没有明确的反转步骤的情况下以正确的顺序进行.