Haskell中便宜的列表操作技术现状是什么？

Question

对于像列表（而不是字符字符串）上的append这样的廉价操作，我会使用Data.DList。

使我犹豫不决的是Hackage上的包标记为“试验性”，最后一次更新是在2009年。

在Haskell中，DList仍然是正确的选择吗？

- LennyStackOverflow

---

你期望哪些操作具有O(1)的时间复杂度？ - augustss

如果你只是想要添加元素，那我推荐使用这个函数：append x y = undefined，它非常快。 :) 所以我猜你想在构建列表之后做一些事情。一旦你告诉我们具体要做什么，我们就可以给你建议。 - augustss

@augustss： :) 这是关于构建和转换结构化文本列表的。不是普通的Data.Text，而是例如'Bold "hi there"'、'Paragraph "Long boring text"'或'Section "Title" "Content..."'这样的列表。 - LennyStackOverflow

@Lenny222 那么，如何构建一棵树，每个叶子节点都有一个文本项，然后每个附加操作都生成一个分支。这样可以获得恒定时间的附加操作。您可以稍后在O(n)时间内将其线性化，即每个附加操作的平摊复杂度为O(1)。 - augustss

Answer 1

使用来自Data.Sequence的Seq。它也有O(1)的cons和snoc，但它是在base中的，被更广泛地使用和测试过。

- Sjoerd Visscher

Answer 2

Data.DList 似乎是在2009年6月20日23:01:49 UTC最后更新的。Hackage上有很多有用的东西被标记为实验性，但我不会担心这个。DList看起来相当稳定。它不使用任何易变的语言扩展，代码实际上相当简单。

所以，我的答案是：是的，DList仍然很好。

- aleator

---

2009年：我的错误，不知何故谷歌将我发送到了旧版本。我想知道在 GHC -> 7.* 升级期间是否已经出现了问题。 - LennyStackOverflow

@Lenny222：我怀疑它是否已经陈旧过时了。差异列表相当简单，而且该程序包似乎没有使用任何 GHC 扩展，除了 CPP 之外。因此不可能出现太多问题。 - John L