使用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']将最后一个元素附加到列表中.它导致运行时从.18s增加到.33s,内存从568MB增加到1.12GB.

所以它确实确实导致了多次遍历.有人可以在理论上证实吗？

Answer 1

您无法从这些数字中得出结论:第一次运行是执行两次遍历,还是一次遍历,其中每个步骤比第二次运行中的单次遍历花费更多时间并分配更多内存.

事实上,后者发生在这里.你可以想到这样的两个评估:

• 在第二个表达式中let t = replicate 9999999 'a' in last t,在每个步骤中,但在最后一个表达式中,last计算其参数,这导致replicate分配cons单元并递减计数器,然后使用cons单元格last.

• 在第一个表达式中let t = replicate 9999999 'a' ++ ['x'] in last t,在每个步骤中,但在最后一个表达式中,last计算其参数,这会导致(++)计算其第一个参数,这会导致replicate分配一个cons单元并递减一个计数器,然后该cons单元被消耗(++)并(++)分配一个新的缺点细胞,然后消耗新的利弊细胞last.

所以第一个表达式仍然是单个遍历,它只是一个每步执行更多工作的表达式.

现在,如果你愿意,你可以将所有这些工作分成"完成的工作last"和"完成的工作(++)",然后称这两个"遍历"; 这对于理解程序完成的工作总量来说是一种有用的方法.但是由于Haskell的懒惰,两个"遍历"实际上是如上所述的交错,因此大多数人会说列表只被遍历一次.