haskell - 惯用的高效 Haskell append ？

Question

列表和 cons 运算符 (:) 在 Haskell 中非常常见。缺点是我们的 friend 。但有时我想添加到列表的末尾。

xs `append` x = xs ++ [x]

遗憾的是，这不是一种有效的实现方式。

我写了Pascal's triangle在 Haskell 中，但我必须使用 ++ [x] 反习语:

ptri = [1] : mkptri ptri
mkptri (row:rows) = newRow : mkptri rows
    where newRow = zipWith (+) row (0:row) ++ [1]

恕我直言，这是一个可爱可读的帕斯卡三角形等等，但是反成语让我感到厌烦。有人可以向我解释一下(最好是给我指出一个很好的教程)对于您想要有效地 append 到末尾的情况，惯用的数据结构是什么？我希望这个数据结构及其方法具有近乎列表般的美感。或者，或者，向我解释为什么这个反习语对于这种情况实际上并没有那么糟糕(如果你相信情况是这样的话)。

<小时/>

[编辑]我最喜欢的答案是Data.Sequence，它确实具有“接近列表的美感”。不知道我对操作所需的严格性有何看法。随时欢迎进一步的建议和不同的想法。

import Data.Sequence ((|>), (<|), zipWith, singleton)
import Prelude hiding (zipWith)

ptri = singleton 1 : mkptri ptri

mkptri (seq:seqs) = newRow : mkptri seqs
    where newRow = zipWith (+) seq (0 <| seq) |> 1

现在我们只需要 List 成为一个类，以便其他结构可以使用它的方法，例如 zipWith ，而无需从 Prelude 中隐藏它或限定它。 :P

Answer 1

请记住，看起来很糟糕的渐近实际上可能并非如此，因为您使用的是惰性语言。在严格的语言中，以这种方式 append 到链表的末尾总是 O(n)。在惰性语言中，只有当你实际遍历到列表的末尾时，它才是 O(n)，在这种情况下，无论如何你都会花费 O(n) 的努力。所以很多时候，懒惰可以拯救你。

这不是保证...例如，k 追加后跟遍历仍将在 O(nk) 中运行，而它本来可以是 O(n+k)。但它确实在某种程度上改变了情况。当立即强制结果时，根据渐近复杂性来考虑单个操作的性能并不总能最终给出正确的答案。