haskell - 为什么这个 Haskell 程序在优化编译时会泄漏空间？

Question

考虑以下玩具程序，它计算单词中字符替换的所有组合，即密码中经常使用的那种。

import Data.Char (isLower, toUpper)

variants :: String -> [String]
variants "" = [""]
variants (c:s) = [c':s' | c' <- subst c, s' <- variants s]
  where subst 'a' = "aA@"
        subst 'e' = "eE3"
        subst 'i' = "iI1"
        subst 'l' = "lL1"
        subst 'o' = "oO0"
        subst 's' = "sS$5"
        subst 'z' = "zZ2"
        subst x | isLower x = [x, toUpper x]
        subst x = [x]

main :: IO ()
main = putStrLn $ show $ length $ variants "redistributables"

我编译它时进行了优化，也没有进行优化:

$ ghc -fforce-recomp -Wall Test.hs -o test0
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking test0 ...

$ ghc -fforce-recomp -O -Wall Test.hs -o test1
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking test1 ...

现在 test0 和 test1 产生相同的输出，但 test1 使用更多的内存，并且大部分时间都花在垃圾回收上:

$ ./test0 +RTS -s 2>&1 | grep total
               2 MB total memory in use (0 MB lost due to fragmentation)
  Productivity  93.2% of total user, 93.3% of total elapsed

$ ./test1 +RTS -s 2>&1 | grep total
             188 MB total memory in use (0 MB lost due to fragmentation)
  Productivity  15.0% of total user, 15.0% of total elapsed

为什么？

我正在使用 GHC 7.4.1；我可能应该使用更新的编译器，但这就是我目前手头有的东西，无论如何，错误可能都在我身上。

Answer 1

你想要

variants (c:s) = [c':s' | c' <- subst c, s' <- variants s]

被编译成外循环和内循环。但 GHC 认为内部循环不以任何方式依赖于外部“循环计数器”。因此，完全惰性转换将内循环从外循环中提升出来。一个相当有效的技巧是隐藏内循环是独立的这一事实。这是通过将内部循环拆分为一个带有虚拟参数的单独函数，并通过将函数标记为 NOINLINE 来隐藏虚拟参数来完成的。然后你可以用外循环计数器调用该函数，GHC 通常不会打扰你。