haskell - 为什么会立即添加到列表中？

Question

我正在阅读有关列表的 Haskell 教程，它声称:

Watch out when repeatedly using the ++ operator on long strings ... Haskell has to walk through the whole list on the left side of ++. ... However, putting something at the beginning of a list using the : operator (also called the cons operator) is instantaneous.

但是，在我看来，事情应该是相反的。

: 必须遍历列表中的所有元素，因为它需要移动所有索引。另一方面，++ 可以只在列表末尾附加一个新元素并完成它，因此是瞬时的。

对理解这句话有帮助吗？

Answer 1

Haskell 中的列表只是一个单链表。例如，Char 列表可以是 [](空列表)，也可以是 c : cs，其中 c 是一个 Char，cs 是一个 Char 列表。要在给定 c 和 cs 的情况下生成 c : cs，所有实现所需要做的就是分配一个带有指示 (: ) 以及指针 c 和 cs 的副本。这非常便宜。