4

当我阅读第 13 章时，Real World Haskell我想到了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的那样保留左操作数，而不是保留左操作数small，但是....我们仍然对每个追加执行遍历。

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

  1. f(f([1..100]))= f([1..100,1])- 遍历 1 次并附加1

  2. [1..100,1,2]- 遍历第二次追加2

有人能告诉我这在时间复杂度上如何更有效吗？（因为space-complexity 不再是因为thunks, like foldl'）

附言

我知道规范的答案，并且我也阅读了这一章，我觉得这很有帮助。
我知道您可以O(1)通过使用 追加到左侧来实现复杂性:，但它不会类似于++.

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

4

1 回答 1

5

你需要对时间更加小心，即当这件事或那件事发生时。

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

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

然后将 4、5 “添加”到增长差异列表的末尾，我们有

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

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

当我们最终完成构建它时，我们通过应用程序将它转换为“正常”列表

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  :    [] ))

根据 的定义(++)。

一个规范的答案：为什么差异列表比常规连接更有效？

甚至a1 = (++ [4]) [1..] 它本身也是一个O(1)操作，a2 = (++ [5]) a1因为a3 = (++ [6]) a2Haskell 是惰性的，并且 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] ++) []))。

于 2019-02-06T08:56:04.857 回答