为什么差异列表比常规连接更有效?

我现在正在通过在线学习你一个haskell书籍,并且已经到了一个章节,作者正在解释一些列表连接可能是不够的:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f 

据说效率不高。 作者提出的解决scheme是使用定义为“差异列表”

 newtype DiffList a = DiffList {getDiffList :: [a] -> [a] } instance Monoid (DiffList a) where mempty = DiffList (\xs -> [] ++ xs) (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs)) 

我很难理解为什么在某些情况下DiffList在计算上比简单的级联更有效率。 有人能够简单地向我解释为什么上面的例子效率很低,DiffList以什么方式解决了这个问题?

在这个问题

 ((((a ++ b) ++ c) ++ d) ++ e) ++ f 

是嵌套。 (++)的应用程序是左嵌套的,这是错误的,右嵌套

 a ++ (b ++ (c ++ (d ++ (e ++f)))) 

不会是一个问题。 那是因为(++)被定义为

 [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys) 

所以要find使用哪个方程,实现必须深入到expression式树中

  (++) / \ (++) f / \ (++) e / \ (++) d / \ (++) c / \ ab 

直到找出左操作数是否为空。 如果不是空的话,它的头被取出并冒泡到顶部,但是左操作数的尾部不被触摸,所以当需要连接的下一个元素时,同样的过程再次开始。

当连接是右嵌套的时候, (++)的左操作数总是在最上面,检查虚空/起泡头是O(1)。

但是,当连接是左嵌套,深度为n层时,要到达第一个元素,必须遍历树的n节点,对于结果的每个元素(来自第一个列表,来自第二个列表的n-1等等。)。

让我们考虑a = "hello"

 hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f 

我们要评估take 5 hi 。 所以首先必须检查是否

 (((a ++ b) ++ c) ++ d) ++ e 

是空的。 为此,必须检查是否

 ((a ++ b) ++ c) ++ d 

是空的。 为此,必须检查是否

 (a ++ b) ++ c 

是空的。 为此,必须检查是否

 a ++ b 

是空的。 为此,必须检查是否

 a 

是空的。 唷。 不是,所以我们可以再次冒泡,组装

 a ++ b = 'h':("ello" ++ b) (a ++ b) ++ c = 'h':(("ello" ++ b) ++ c) ((a ++ b) ++ c) ++ d = 'h':((("ello" ++ b) ++ c) ++ d) (((a ++ b) ++ c) ++ d) ++ e = 'h':(((("ello" ++ b) ++ c) ++ d) ++ e) ((((a ++ b) ++ c) ++ d) ++ e) ++ f = 'h':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f) 

对于'e' ,我们必须重复一遍,对于'l'也是…

画一个树的一部分,冒泡就像这样:

  (++) / \ (++) c / \ 'h':"ello" b 

成为第一

  (++) / \ (:) c / \ 'h' (++) / \ "ello" b 

接着

  (:) / \ 'h' (++) / \ (++) c / \ "ello" b 

一路回到顶端。 最终成为顶层(:)的右侧子树的结构与原始树的结构完全相同,除非最左侧的列表为空,

  (++) / \ [] b 

节点被折叠到b

因此,如果您有短列表的左嵌套连接,则连接变为二次,因为连接的头部是O(嵌套深度)操作。 一般来说,一个左嵌套的连接

 (...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1 

O(sum [i * length a_i | i <- [1 .. d]])来完全评估。

有了差异列表(为了简化说明,不包含新types的包装),组合是否是左嵌套并不重要

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) 

或者右嵌套。 一旦遍历了嵌套到达(a ++) ,那么(++)被悬挂在expression式树的顶部,因此再次获得a的每个元素都是O(1)。

事实上,只要你需要第一个元素,整个构图就与差异列表重新关联,

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f 

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f (((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f) ((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f)) (a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f))) a ++ (b ++ (c ++ (d ++ (e ++ f)))) 

在此之后,每个列表都是前一个列表被消耗后的最高级(++)左侧操作数。

重要的是,前置函数(a ++)可以在不检查它的论点的情况下开始产生结果,从而重新关联

  ($) / \ (.) f / \ (.) (e ++) / \ (.) (d ++) / \ (.) (c ++) / \ (a ++) (b ++) 

通过

  ($)--------- / \ (.) ($) / \ / \ (.) (d ++) (e ++) f / \ (.) (c ++) / \ (a ++) (b ++) 

  ($) / \ (a ++) ($) / \ (b ++) ($) / \ (c ++) ($) / \ (d ++) ($) / \ (e ++) f 

不需要知道任何关于最终列表f的组合函数,所以它只是一个O(depth)重写。 然后是顶层

  ($) / \ (a ++) stuff 

  (++) / \ a stuff 

并且可以一步获得a所有元素。 在这个例子中,我们有纯粹的左嵌套,只需要重写一次。 如果不是(例如) (d ++)那个地方的函数是左嵌套合成, (((g ++) . (h ++)) . (i ++)) . (j ++) (((g ++) . (h ++)) . (i ++)) . (j ++) ,顶层重新关联会使这个原型保持原样,并且在所有以前的列表被消耗完之后,当它成为顶层($)的左操作数时,这将被重新关联。

所有重关联所需要的全部工作是O(number of lists) ,所以连接的总成本是O(number of lists + sum (map length lists)) 。 (这意味着你可以通过插入大量的左嵌套([] ++)来带来不好的performance。)

 newtype DiffList a = DiffList {getDiffList :: [a] -> [a] } instance Monoid (DiffList a) where mempty = DiffList (\xs -> [] ++ xs) (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs)) 

只是把这个包起来,这样抽象的处理就更方便了。

 DiffList (a ++) `mappend` DiffList (b ++) ~> DiffList ((a ++) . (b++)) 

请注意,只有在不需要检查参数来开始生成输出的函数时,如果任意函数被包装在DiffList ,那么您就没有这样的效率保证。 特别是,如果构成右嵌套,附加( (++ a) ,wrapping或not)可以创build(++)左嵌套树,所以如果DiffList构造函数是裸露。

这可能有助于查看连接的定义:

 [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys) 

正如你所看到的,为了连接两个列表,你需要通过左边的列表并创build一个“拷贝”,这样就可以改变它的结束(这是因为你不能直接改变旧的结尾名单,由于不变性)。

如果你以正确的联合方式进行连接,没有问题。 一旦插入,一个列表将永远不会再被触及(注意++的定义从不检查右边的列表),因此每个列表元素只被插入“一次”,总的时间为O(N)。

 --This is O(n) (a ++ (b ++ (c ++ (d ++ (e ++ f))))) 

但是,如果以左结合的方式进行连接,那么每当您添加另一个列表片段到最后时,“当前”列表将不得不被“拆除”和“重build”,每个列表元素将在迭代时迭代它被插入,以及将来的片段都被追加了!就像你在C中连续多次调用strcat一样。


至于差异名单,诀窍是他们最后保留一个明确的“漏洞”。 当您将DList转换回正常列表时,您可以将其传递到洞中,然后就可以开始了。 另一方面,正常列表总是以[]结尾,所以如果你想改变它(当连接时),那么你需要翻开列表来达到这一点。

差异列表与函数的定义起初看起来有点吓人,但实际上很简单。 你可以从面向对象的angular度来看待它们,把它们看作是不透明的对象“toList”方法,它接收你应该插入到洞中的列表,最后返回DL的内部前缀加上提供的尾部。 这是有效的,因为在完成所有事情的转换之后,您只需要将“漏洞”插入即可。