list - 用于将数据 append 到列表末尾的 Data.Sequence 与 Data.DList

Question

我正在编写一些需要经常 append 到列表末尾的代码。我知道使用“++”是低效的。因此，我通过 append 到头部来反向构建列表，然后在完成后将其反转。我认为这是一种常见的初学者策略。

我宁愿以正确的顺序开始构建它——但这意味着切换到一个新的数据结构。我正在考虑为我的容器使用 Data.Sequence 或 Data.DList。我的列表由严格的 int 对组成，我不需要随机访问它。 Data.Sequence 和 Data.DList 的相对优点是什么，我应该考虑其他容器吗？

Answer 1

是否使用Data.Sequence或 DList取决于您将如何使用结果列表。 DList在构建序列时非常有用，例如在 Writer 中计算，最后转换为列表并使用它。但是，如果您需要使用中间结果，例如:

f (foo ++ bar)
+ f (foo ++ bar ++ baz)
+ f (foo ++ bar ++ baz ++ quux)

然后 DList非常糟糕，因为它每次都需要重新计算脊椎。 Data.Sequence在这种情况下是更好的选择。 Data.Sequence如果您需要从序列中删除元素也更好。

但也许你甚至不需要做出这个决定。在计算结束时反转列表在 ML 和 Scheme 等严格的函数式语言中很常见，但在 Haskell 中则不然。以这两种写法为例 map :

map_i f xs = reverse $ go [] xs
    where
    go accum [] = accum
    go accum (x:xs) = go (f x : accum) xs

map_ii f [] = []
map_ii f (x:xs) = f x : map_ii f xs

用严格的语言， map_ii会很可怕，因为它使用线性堆栈空间，而 map_i是尾递归的。但是因为 Haskell 是懒惰的， map_i是低效的。 map_ii可以消耗输入的一个元素并产生输出的一个元素，而 map_i在产生任何输出之前消耗整个输入。

尾递归并不是 Haskell 中高效实现的 chalice 。在生成像列表这样的数据结构时，您实际上希望是协同递归的；也就是说，在构造函数的应用程序下进行递归调用(例如上面的 f x : map_ii f xs)。

因此，如果您发现自己在尾递归函数之后进行了反转，请查看是否可以将全部因素分解为核心递归函数。