haskell - 避免多次列表遍历的好处

Question

我在函数式语言中看到过许多关于处理列表并构造函数以在接收到一些附加值(通常在生成函数时不存在)后对其元素执行某些操作的示例，例如:

• Calculating the difference between each element and the average

  (“惰性求值”下的最后 2 个示例)

• 以严格的函数语言(例如 ML/OCaml、to avoid traversing the first list more than once)暂存列表追加

  (标题为“分期”的部分)

• 使用foldr将一个列表与另一个列表进行比较(即生成一个函数来将另一个列表与第一个列表进行比较)

  listEq a b = foldr comb null a b
    where comb x frec [] = False
          comb x frec (e:es) = x == e && frec es
  cmp1To10 = listEq [1..10]
  

在所有这些示例中，作者通常都提到了仅遍历原始列表一次的好处。但我无法阻止自己思考“当然，你不是遍历 N 个元素的列表，而是遍历 N 个评估的链，那又怎样？”。我知道它一定有一些好处，有人可以解释一下吗？

<小时/>

编辑:感谢两位的回答。不幸的是，这不是我想知道的。我将尝试澄清我的问题，这样它就不会与有关创建中间列表的(更常见的)问题(我已经在各个地方读到过)相混淆。也感谢您纠正我的帖子格式。

我对构建一个应用于列表的函数的情况感兴趣，在这种情况下，您还没有评估结果的必要值(无论是否是列表)。那么你就无法避免生成对每个列表元素的引用(即使列表结构不再被引用)。并且您具有与以前相同的内存访问权限，但不必解构列表(模式匹配)。

例如，请参阅上述 ML 书中的“staging”章节。我在 ML 和 Racket 中尝试过，更具体地说是“append”的分阶段版本，它遍历第一个列表并返回一个函数以在尾部插入第二个列表，而无需多次遍历第一个列表。令我惊讶的是，即使考虑到它仍然必须复制列表结构，因为每种情况下的最后一个指针都不同，但它的速度要快得多。

以下是map的一个变体，应用于列表后，更改功能时应该会更快。由于 Haskell 并不严格，我必须强制对 cachedList 中的 listMap [1..100000] 进行评估(或者可能不会，因为在第一个应用程序之后，它仍然应该存在于内存中)。

listMap = foldr comb (const [])
  where comb x rest = \f -> f x : rest f

cachedList = listMap [1..100000]
doubles = cachedList (2*)
squares = cachedList (\x -> x*x)

-- print doubles and squares
-- ...

我知道在 Haskell 中，使用 comb xrest f = ... 与 comb xrest =\f 没有什么区别(如果我错了，请纠正我) -> ...，但我选择这个版本是为了强调这个想法。

更新:经过一些简单的测试，我在 Haskell 中没有发现执行时间有任何差异。那么问题只是关于严格的语言，例如Scheme(至少是我测试过的Racket实现)和ML。

Answer 1

基本上，在循环体中执行一些额外的算术指令比执行一些额外的内存读取要便宜。

遍历意味着进行大量的内存访问，所以做的越少越好。融合遍历可减少内存流量，并增加直线计算负载，从而获得更好的性能。

具体来说，考虑这个程序来计算列表上的一些数学:

go :: [Int] -> [Int]
go = map (+2) . map (^3)

显然，我们通过两次遍历列表来设计它。在第一次和第二次遍历之间，结果被存储在中间数据结构中。然而，它是一个惰性结构，因此只消耗 O(1) 内存。

现在，Haskell 编译器立即将两个循环融合为:

go = map ((+2) . (^3))

这是为什么呢？毕竟，两者的复杂度都是O(n)，对吧？区别在于常数因子。

考虑这个抽象:对于第一个管道的每个步骤，我们执行以下操作:

  i <- read memory          -- cost M
  j = i ^ 3                 -- cost A
  write memory j            -- cost M
  k <- read memory          -- cost M
  l = k + 2                 -- cost A
  write memory l            -- cost M

因此我们支付 4 次内存访问和 2 次算术运算。

对于融合结果，我们有:

  i <- read memory          -- cost M
  j = (i ^ 3) + 2           -- cost 2A
  write memory j            -- cost M

其中 A 和 M 是对 ALU 和内存访问进行数学计算的常数因子。

还有其他常数因子(两个循环分支)而不是一个。

因此，除非内存访问是免费的(从长远来看，它不是免费的)，否则第二个版本总是更快。

请注意，对不可变序列进行操作的编译器可以实现数组融合，即为您执行此操作的转换。 GHC就是这样一个编译器。