list - 使用 Haskell 的 (++) 运算符追加到列表是否会导致多个列表遍历？

Question

使用 (++) 附加到 Haskell 列表是否会导致列表被多次遍历？

我在 GHCI 中尝试了一个简单的实验。

第一次运行:

$ ghci
GHCi, version 7.8.4: http://www.haskell.org/ghc/  :? for help
Prelude> let t = replicate 9999999 'a' ++ ['x'] in last t
'x'
(0.33 secs, 1129265584 bytes)

第二次运行:

$ ghci
GHCi, version 7.8.4: http://www.haskell.org/ghc/  :? for help
Prelude> let t = replicate 9999999 'a' in last t
'a'
(0.18 secs, 568843816 bytes)

唯一的区别是 ++ ['x'] 将最后一个元素附加到列表中。它导致运行时间从 0.18 秒增加到 0.33 秒，内存从 568MB 增加到 1.12GB。

所以看起来确实是造成了多次遍历。有人可以根据更多理论依据进行确认吗？

Answer 1

您无法从这些数字得出结论，第一次运行是否进行了两次遍历，或者一次遍历比第二次运行中的一次遍历花费更多时间并分配更多内存。

事实上，这里发生的是后者。你可以这样想这两个评估:

• 在第二个表达式 let t = replicate 9999999 'a' in last t 中，在除最后一步之外的每个步骤中，last 计算它的参数，它导致 replicate 分配一个 cons cell 并递减一个计数器，然后 cons cell 被 last 消耗。

• 在第一个表达式中 let t = replicate 9999999 'a'++ ['x'] in last t，在除最后一步之外的每个步骤中，last 计算它的参数，这导致 (++) 计算它的第一个参数，这导致 replicate 分配一个 cons 单元并递减一个计数器，然后那个 cons 单元被 (++) 使用，(++) 分配一个新的 cons cell，然后这个新的 cons cell 被 last 使用。

所以第一个表达式仍然是一个单一的遍历，它只是每一步做更多的工作。

现在，如果您愿意，可以将所有这些工作分成“last 完成的工作”和“(++) 完成的工作”，然后调用那两个“遍历”；这可能是了解程序完成的工作总量的有用方法。但是由于 Haskell 的惰性，两次“遍历”确实如前所述交错进行，所以大多数人会说列表只遍历一次。