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

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

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；我可能应该使用较新的编译器，但这是我目前很方便的方法，无论如何，故障可能出在我身上。

最佳答案

你要

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

被编译成一个外部循环和一个内部循环。但是GHC认为内部循环不以任何方式依赖于外部“循环计数器”。因此，完全懒惰变换将内循环从外循环中移出。一个相当有效的技巧是隐藏内循环是独立的这一事实。这可以通过以下方式完成:将内部循环拆分为带有哑元参数的单独函数，然后通过将函数标记为NOINLINE来隐藏虚拟对象。然后，您可以使用外部循环计数器调用该函数，GHC通常会避免与您发生困惑。

关于haskell - 为什么在进行优化编译时此Haskell程序会泄漏空间？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31012133/