Data.Sequence与Data.DList,用于将数据附加到列表的末尾

Question

我正在编写一些需要经常附加到列表末尾的代码.我知道使用"++"是低效的.因此,我通过附加到头部向后构建列表,然后在完成后反转它.我认为这是一个常见的初学者策略.

我宁愿以正确的顺序构建它 - 但这意味着切换到新的数据结构.我正在考虑为我的容器使用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中有效实现的圣杯.在生成像列表这样的数据结构时,您实际上希望是共同的 ; 也就是说,在构造函数的应用程序(例如f x : map_ii f xs上面)下面进行递归调用.

因此,如果您发现自己在尾递归函数后反转,请查看是否可以将整个因子分解为一个corecursive函数.