6

假设我们有以下内容:

l = map f (map g [1..100])

我们想做:

head l

所以我们得到:

head (map f (map g [1..100]))

现在,我们必须得到这个的第一个元素。map定义如下:

map f l = f (head l) : (map f (tail l))

那么我们得到:

f (head (map g [1..100]))

然后再次申请:

f (g (head [1..100]))

这导致

f (g 1)

仅仅由于懒惰,没有形成中间列表。

这个分析正确吗?并具有这样的简单结构:

foldl' ... $ map f1 $ map f2 $ createlist

是否曾经创建过中间列表,即使没有“列表融合”?(我认为懒惰应该轻松消除它们)。


我能看到保留列表的唯一原因是我们这样做了:

l' = [1..100]
l = map f (map g l')

如果在其他地方使用,我们可能想要保留l'的地方。然而,在l'上面的例子中,编译器意识到重新计算上面的列表而不是存储它应该是相当简单的。

4

2 回答 2

7

当中间数据结构昂贵时,融合受益最大。当传递的结构是惰性的,并且以顺序方式访问时,结构可能相对便宜(就像列表一样)。

  • 对于惰性结构,融合消除了创建 thunk 的常量因素,并立即对它进行垃圾收集。
  • 对于严格的结构,融合可以消除O(n)的工作。

因此,最大的好处是对于严格的数组和类似的结构。然而,即使融合惰性列表仍然是一个胜利,因为增加了数据局部性,因为更少的中间结构被分配为 thunk。

于 2012-06-08T11:49:40.043 回答
7

在您的map示例中,创建了列表单元格,然后立即进行垃圾收集。使用列表融合,不需要 GC 或 thunk 操作(它们都不是免费的)。

于 2012-06-08T08:45:43.780 回答