了解差异列表的概念

Question

当我阅读 Real World Haskell 的第 13 章时，我想到了 Difference Lists 的概念。
作者说，在命令式语言中，如果我们想将一个元素附加到列表中，成本将为 O(1)，因为我们将保留指向最后一个元素的指针。但是在 Haskell 中，我们有 immutable 个对象，所以我们每次都需要遍历列表并在末尾附加元素，因此 0(n).

而不是[1,2,3]++[4]++[5]
我们可以使用部分应用程序：(++4).(++5) [1,2,3]。

我不明白这如何更有效，因为：
- 当我做 (++[5]) [1,2,3] 它仍然是 O(n) 然后另一个 0(n) 为 (++4)

引用

There are two very interesting things about this approach. The first is that the cost of a partial application is constant, so the cost of many partial applications is linear. The second is that when we finally provide a [] value to
unlock the final list from its chain of partial applications, application 
proceeds from right to left. This keeps the left operand of (++) small, and so 
the overall cost of all of these appends is linear, not quadratic

我知道这种方法会很急切，所以我们没有像作者所说的那样保留 yet to be applied methods 的 thunk，而是保留左操作数 small，但是......我们仍然对每个追加执行遍历。

给定一个列表：[1...100] 并且想要追加 1,2 我仍然会遍历它 2 次因为我会 :

f(f([1..100]))= f([1..100,1]) - 遍历 1 次并追加 1
[1..100,1,2]-遍历第二次追加2

谁能告诉我这在时间复杂度上如何更有效率？（因为space-复杂性是由于不再有thunks，像foldl'）

P.S

我知道规范的答案，我还阅读了 this chapter，我发现它非常有帮助。
我知道您可以通过在左侧追加来实现 O(1) 复杂性使用 :，但它不会类似于 ++。

如果我在 a= [1,2,3] 上使用 f=(:) :
(f 4 . f 5) $ a
我可以说我每次追加都有 0(1) 效率，因为我总是在左边追加，但我不会得到 [1,2,3,4,5]，我会得到 [5,4,1,2,3] ，那么在这种情况下 difference list 如何更有效地附加一个元素的单一操作？

Answer 1

你需要更加注意时间，即什么时候这个或那个事情正在发生。

我们不是从列表 [1,2,3] 开始，而是从不同的列表开始

f1 = ([1,2,3] ++)

然后到 "add" 4、5，到不断增长的 difference 列表的末尾，我们有

f2 = f1 . ([4] ++)
f3 = f2 . ([5] ++)

每个这样的添加 到不断增长的差异列表的末尾 是 O(1).

当我们最终构建完成后，我们通过应用程序将其转换为 "normal" 列表

xs = f3 []    -- or f3 [6..10] or whatever

然后，仔细地，我们得到

xs = ((([1,2,3] ++) . ([4] ++)) . ([5] ++)) []
   =  (([1,2,3] ++) . ([4] ++)) ( ([5] ++)  [] )
   =   ([1,2,3] ++) ( ([4] ++)  ( ([5] ++)  [] ))
   =     1:2:3:     (   4  :    (   5  :    [] ))

根据(++)的定义。

一个规范的答案：Why are difference lists more efficient than regular concatenation?

即使 a1 = (++ [4]) [1..] 本身也是一个 O(1) 操作，a2 = (++ [5]) a1 和 a3 = (++ [6]) a2，因为 Haskell 是懒惰的，thunk 创建是 O(1).

只有当我们访问最终结果时，整个操作才会变成二次操作，因为访问 ++ 结构不会重新排列它——它仍然是左嵌套的，所以 二次操作 从顶部重复访问。

通过将左嵌套 . 结构应用到 [] 来转换为普通列表会在内部将该结构重新排列为右嵌套 $ 结构，如规范中所述答案，所以从顶部重复访问这样的结构是线性的。

所以区别在于 ((++ [5]) . (++ [4])) [1,2,3]（差）和 ((([1,2,3] ++) . ([4] ++)) . ([5] ++)) []（好）。构建函数链 ((++ [4]) . (++ [5])) 本身是线性的，是的，但它创建了一个二次结构以完全访问。

但是 ((([1,2,3] ++) . ([5] ++)) . ([4] ++)) [] 变成了 ([1,2,3] ++) (([5] ++) (([4] ++) []))。

了解差异列表的概念

Understanding the concept of difference lists

optimization

haskell

difference-lists