如何最简单地将元素添加到列表末尾？

Question

:: : 'a -> 'a list -> 'a list函数用于在列表的开头添加元素，那么是否有函数可以将元素添加到末尾呢？如果没有，我猜List.rev (element::(List.rev list))是最简单的方法？

谢谢！

- SoftTimur

Answer 1

没有标准函数来实现这个的原因是，在列表末尾添加元素是一种反模式（也称为“snoc列表”或Schlemiel the Painter算法）。在列表末尾添加元素需要对列表进行完全复制。在列表前面添加元素只需要分配一个单元格——新列表的尾部可以指向旧列表。

话虽如此，最简单的方法是：

let append_item lst a = lst @ [a]

- Chris Conway

Answer 2

list@[element] 应该能够正常工作。@ 是连接列表的符号。

- Adi

Answer 3

考虑到这个操作是线性的，您不应该在代码的“热”部分使用它，因为性能很重要。在冷却部分中，建议使用list @ [element]，如Adi所建议的那样。在热部分中，重写您的算法，以便您不需要执行该操作。

通常的做法是在处理期间按相反顺序累积结果，然后在返回结果之前将整个累积列表倒转。如果您有N个处理步骤（每个步骤向列表中添加一个元素），则可以将倒置的线性成本摊分在N个元素上，因此您可以保持线性算法而不是二次方算法。

在某些情况下，另一种有效的技术是按相反顺序处理元素，使得累积的结果无需显式地倒置即可呈现正确的顺序。

- gasche