使用 Haskell 的 (++) 运算符追加到列表是否会导致多个列表遍历？
Does using Haskell's (++) operator to append to list cause multiple list traversals?
使用 (++) 附加到 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。
看来确实是造成了多次遍历。有人可以根据更多理论依据进行确认吗？
您无法从这些数字得出结论，第一个 运行 是否进行了两次遍历，或者在一次遍历中每一步都比第二个 运行 中的单个遍历花费更多时间并分配更多内存].
事实上，这里发生的是后者。你可以把这两个评价想成这样：
在第二个表达式 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 单元被 (++) 消耗并且 (++) 分配一个新的 cons 单元，然后该新的 cons 单元被消耗通过 last.
所以第一个表达式仍然是一个单一的遍历，它只是每一步做更多的工作。
现在，如果您愿意，可以将所有这些工作分成 "the work done by last" 和 "the work done by (++)"，并将这两个称为 "traversals"；这可能是了解程序完成的工作总量的有用方法。但是由于Haskell的懒惰，这两个"traversals"确实如上文所述是交错的，所以一般人会说只遍历了一次链表。
我想谈谈当我们启用优化时会发生什么，因为它可以从根本上改变程序的性能特征。我将查看 ghc -O2 Main.hs -ddump-simpl -dsuppress-all 生成的 Core 输出。此外，我 运行 使用 +RTS -s 编译程序以获取有关内存使用情况和 运行 宁时间的信息。
与 GHC 7.8.4 代码的两个版本 运行 在相同的时间量和相同的堆分配量。那是因为 replicate 9999999 'a' 和 ++ ['x'] 被替换为 genlist 9999999，其中 genlist 看起来像下面这样（不完全一样，因为我使用了原始核心的自由翻译）：
genlist :: Int -> [Char]
genlist n | n <= 1 = "ax"
| otherwise = 'a' : genList (n - 1)
由于我们在一步中进行生成和连接，因此我们只为每个列表单元分配一次。
在 GHC 7.10.1 中，我们对列表处理进行了全新的优化。现在我们的两个程序都分配了与 print $ "Hello World" 程序一样多的内存（在我的机器上大约 52 Kb）。这是因为我们完全跳过了列表创建。现在 last 也被融合掉了；我们接到电话 getlast 9999999，其中 getlast 是：
getlast :: Int -> Char
getlast 1 = 'x'
getlast n = getlast (n - 1)
在可执行文件中，我们将有一个从 9999999 倒数到 1 的小机器代码循环。 GHC 不够聪明，无法跳过所有计算并直接返回 'x'，但它仍然做得很好，最后它给了我们一些与原始代码截然不同的东西。
使用 (++) 附加到 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。
看来确实是造成了多次遍历。有人可以根据更多理论依据进行确认吗？
您无法从这些数字得出结论，第一个 运行 是否进行了两次遍历，或者在一次遍历中每一步都比第二个 运行 中的单个遍历花费更多时间并分配更多内存].
事实上，这里发生的是后者。你可以把这两个评价想成这样：
在第二个表达式
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 单元被(++)消耗并且(++)分配一个新的 cons 单元，然后该新的 cons 单元被消耗通过last.
所以第一个表达式仍然是一个单一的遍历，它只是每一步做更多的工作。
现在，如果您愿意，可以将所有这些工作分成 "the work done by last" 和 "the work done by (++)"，并将这两个称为 "traversals"；这可能是了解程序完成的工作总量的有用方法。但是由于Haskell的懒惰，这两个"traversals"确实如上文所述是交错的，所以一般人会说只遍历了一次链表。
我想谈谈当我们启用优化时会发生什么，因为它可以从根本上改变程序的性能特征。我将查看 ghc -O2 Main.hs -ddump-simpl -dsuppress-all 生成的 Core 输出。此外，我 运行 使用 +RTS -s 编译程序以获取有关内存使用情况和 运行 宁时间的信息。
与 GHC 7.8.4 代码的两个版本 运行 在相同的时间量和相同的堆分配量。那是因为 replicate 9999999 'a' 和 ++ ['x'] 被替换为 genlist 9999999，其中 genlist 看起来像下面这样（不完全一样，因为我使用了原始核心的自由翻译）：
genlist :: Int -> [Char]
genlist n | n <= 1 = "ax"
| otherwise = 'a' : genList (n - 1)
由于我们在一步中进行生成和连接，因此我们只为每个列表单元分配一次。
在 GHC 7.10.1 中，我们对列表处理进行了全新的优化。现在我们的两个程序都分配了与 print $ "Hello World" 程序一样多的内存（在我的机器上大约 52 Kb）。这是因为我们完全跳过了列表创建。现在 last 也被融合掉了；我们接到电话 getlast 9999999，其中 getlast 是：
getlast :: Int -> Char
getlast 1 = 'x'
getlast n = getlast (n - 1)
在可执行文件中，我们将有一个从 9999999 倒数到 1 的小机器代码循环。 GHC 不够聪明，无法跳过所有计算并直接返回 'x'，但它仍然做得很好，最后它给了我们一些与原始代码截然不同的东西。