我目前正在在线阅读Learn you a 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's 也是...
绘制树的一部分，冒泡是这样的：
(++)
/ \
(++) c
/ \
'h':"ello" b
成为第一
(++)
/ \
(:) c
/ \
'h' (++)
/ \
"ello" b
接着
(:)
/ \
'h' (++)
/ \
(++) c
/ \
"ello" b
一直回到顶部。最终成为顶层右孩子的树(:)的结构与原树的结构完全相同，除非最左边的列表为空，当
(++)
/ \
[] b
节点被折叠到 just b。
因此，如果您有短列表的左嵌套串联，则串联变为二次，因为要获得串联的头部是 O（嵌套深度）操作。一般来说，左嵌套的串联
(...((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++))
请注意，它仅对不需要检查其参数即可开始生成输出的函数有效，如果任意函数包装在DiffLists 中，则没有这样的效率保证。特别是，附加 ( (++ 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 转换回普通列表时，您会将您想要的内容传递给它，它就可以开始使用了。另一方面，普通列表总是在最后堵住这个洞，[]所以如果你想改变它（连接时），那么你需要撕开列表才能到达那一点。
用函数定义差异列表起初看起来很吓人，但实际上非常简单。您可以从面向对象的角度查看它们，将它们视为不透明对象“toList”方法，该方法接收您应该插入到孔中的列表，最后返回 DL 的内部前缀加上提供的尾部。它很有效，因为您只有在完成所有转换后才最终堵住“洞”。