为什么差异列表比常规连接更有效？
我现在正在通过在线学习你一个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的内部前缀加上提供的尾部。 这是有效的，因为在完成所有事情的转换之后，您只需要将“漏洞”插入即可。
