我目前的工作我的方式，通过学习你Haskell的在线预订，并且已经到了一个章节，其中笔者解释说，一些列表级联可能是低效的：例如
((((a ++ b) ++ c) ++ d) ++ e) ++ f
据说是低效的。 笔者想出了解决的方法是用“差异表”定义为
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)
所以要找到使用哪个公式，实现必须潜入表达式树
(++)
/ \
(++) f
/ \
(++) e
/ \
(++) d
/ \
(++) c
/ \
a b
直到找出是否左操作数为空。 如果不是空的，它的头被取出并冒泡到顶部，但左操作数的尾部保持不变，所以当级联的一个元素时要求，同样的程序再次启动。
当级联是右嵌套，的左操作数(++)总是在顶部，和/检查空虚冒泡头部被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]])全面评估。
随着差异表（SAN的NEWTYPE包装的简化说明），这不是很重要的组成是否为左嵌套
((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++)
或右嵌套。 一旦你已经走过的嵌套到达(a ++)即(++)被提升到表达式树的顶部，在各部分，使得获得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)) 。 （这意味着你可以把不好的性能这也通过插入了很多深左嵌套([] ++)
该
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 S，你有没有这样的效率保证。 特别是，追加（ (++ a)包裹与否）可以创建左嵌套树(++)时，由右嵌套，这样你就可以创建O(n²)串联与行为，如果DiffList构造函数裸露。
这可能有助于看看级联的定义：
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
正如你所看到的，为了连接两个列表，你需要去在左侧列表，并创建一个它的“复制”，只是让你可以改变它的结束（这是因为你不能直接改变旧的结束列表中，由于不变性）。
如果你在正确的关联方式做你的串连，是没有问题的。 一旦插入，名单将永远不会有再次触摸（注意如何++的定义从来没有检查右侧的列表），这样每个列表元素只办理O的总时间（N）插入的‘一次’。
--This is O(n)
(a ++ (b ++ (c ++ (d ++ (e ++ f)))))
但是，如果你在一个左结合的方式做串联，然后“当前”名单将不得不“拆除”和“重建”，“每次添加另一个列表片段进行到底。每个列表元素将在何时被迭代它插入每当未来片段附加，以及！这就像你用C得到此问题，如果你天真地调用strcat的多次连续。
至于差异表，关键是他们那种保持一个明确的“洞”结尾。 当转换DLIST回到正常的列表中，您通过它，你想在什么洞，这将是蓄势待发。 普通列表，在另一方面，始终堵住孔与结束[]所以如果你想改变它（串联时），那么你需要撕开列表中去这一点。
差的定义与功能可以先看吓人列出，但它实际上是非常简单的。 您可以从一个角度面向对象的点他们的思维为接收，你应该在孔底插入返回DL的内部前缀加上系统提供的尾巴名单不透明的物体“toList”方法进行查看。 这是高效的，因为你只有你做的一切转换后的一端插入“洞”。
