haskell - 为什么生成二进制序列的一种方法比另一种更快？

Question

我想生成长度为 n 的所有可能的二进制序列作为列表。我想出了两种方法来做到这一点。我更喜欢第二个，因为它看起来更容易阅读，但我不知道为什么它比第一个慢得多。

bin_seqs_1 :: Int -> [[Int]]
bin_seqs_1 n = iterate add_bit [[]] !! n
    where add_bit seqs = [b : seq | seq <- seqs, b <- [-1,1]]

bin_seqs_2 :: Int -> [[Int]]
bin_seqs_2 n = sequence $ replicate n [-1,1]

main :: IO ()
main = putStrLn $ show $ bin_seqs_2 23

当我使用优化进行编译并使用 bin_seqs_1 运行(将输出重定向到/dev/null)时，需要 13 秒。对于 bin_seqs_2，需要 29 秒。

为什么第二种方法慢这么多？

编辑:所以这与 sequence 的实现有关。如果我重新定义序列以首先评估列表的尾部，然后评估头部，性能与 bin_seqs_1 相当

bin_seqs_3 n = sequence $ replicate n [-1,1]
    where sequence ms = foldr k (return []) ms
          k m m' = do { xs <- m'; x <- m; return (x:xs) }

但我仍然不明白为什么在“k”函数中，先评估 xs 然后 x 比评估 x 然后 xs 快得多(如 Control.Monad 中所做的那样)。

Answer 1

这是对“为什么第二种方法慢得多？”部分的部分回答

当对列表融合的性能有疑问时，请使用 coredump，Luke!这很容易。

给定test.hs

module Test (_1_bin_seqs, _2_bin_seqs) where

_1_bin_seqs :: Int -> [[Int]]
_1_bin_seqs n = iterate add_bit [[]] !! n
    where add_bit seqs = [b : seq | seq <- seqs, b <- [-1,1]]

_2_bin_seqs :: Int -> [[Int]]
_2_bin_seqs n = sequence $ replicate n [-1,1]

你必须跑

$ ghc test.hs -fforce-recomp -O2 -ddump-simpl -dsuppress-all

• -fforce-recomp - 始终重建
• -O2 - 首选优化级别
• -ddump-simpl - 将核心代码输出到 stdout
• -dsuppress-all - 使输出可供人类读取
• -ddump-rule-rewrites -(可选)显示使用的代码重写规则

注释模块导入您可以控制要核心转储的函数。您会看到 GHC 将第一个版本转换为 iterate + 循环，而第二个版本则不太好。