我目前正在在线阅读《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 如何解决这个问题吗？
在IT技术中存在的问题
((((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(nesting-depth)操作。一般来说，左嵌套连接的连接
(...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1
评估完全需要O(sum [i * length a_i | i <- [1 .. d]])。
使用差异列表（省略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 ++)，则顶层重新关联会保持不变，并且在所有前面的列表都被消耗后成为顶层 ($) 的左操作数时，就会重新关联它。
所有重新关联所需的总工作量为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 中，则没有这样的效率保证。特别地，附加（(++ a)，无论是否被包装）可以创建左嵌套的树形结构 (++) 当组合成右嵌套时，因此如果 DiffList 构造函数暴露出来，则可以通过它创建 O(n²) 的连接行为。
可能有助于查看连接的定义：
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
正如您所看到的，在连接两个列表时，您需要遍历左侧列表并创建其"副本"，以便您可以更改其结尾（这是因为由于不可变性，您无法直接更改旧列表的结尾）。
如果您通过右关联方式执行连接，则没有问题。插入后，列表将永远不必再次操作（请注意，++的定义从不检查右侧列表），因此每个列表元素仅被插入一次，总时间为O（N）。
--This is O(n)
(a ++ (b ++ (c ++ (d ++ (e ++ f)))))
DiffList类型的Semigroup实例，您就不再需要在Monoid类型类中定义mappend了，并且您应该这样做。Semigroup类型类的(<>)运算符继承自mappend。 - Redu