如何在Double的每个元素列表的例子中控制懒惰

Question

我试图解决Haskell List任务中的每个元素的复制,并将其作为一个完整的程序,将列表写入标准输出

这是我的解决方案

main :: IO ()
main = getList >>= return . doubleEachItem >>= putStrLn . show

getList = return [1,3,5]

doubleEachItem :: [Int] -> [Int]
doubleEachItem = foldr (++) [] . map (take 2 . repeat)

但是当我尝试处理真正很长的清单时

getList = return . take 10000000000 $ repeat 15

程序因内存不足错误而终止.

问题是:我如何改进程序,以便能够处理任何大小的列表？

编辑:

我认为程序崩溃了,因为我用runghc命令运行它.在这种情况下,ghc消耗大约3G字节的内存并被操作系统杀死.崩溃后的输出文件只有大约0.6GBytes.我不明白这种行为的原因.

当我将程序编译为本机可执行文件ghc haskell03.hs -o haskell03并通过重定向到文件来执行它时,./haskell03 >out03.txt它完全在恒定的内存空间中运行并生成速度大约为20MBytes/sec的输出文件.程序完成后,输出文件需要57GBytes.总执行时间为47分钟.

Answer 1

哦! 我想我知道发生了什么事.这很微妙.

runghc在解释模式下运行,就好像你已经加载了一个运行文件ghci.getList是一个顶级绑定,因此它的值(以及它引用的所有值)都被缓存.这意味着GHC正试图缓存整个100亿元素阵列.

您可能会认为,如果您列出了列表,它将起作用:

main = putStrLn . show . doubleEachElement $ [1..10^10]

但不是这样,因为它main也是一个顶级绑定,并且它引用了[1..10^10],所以该列表的巨型展开版本也将被缓存在那里.

一般规则是,当某些内容不依赖于输入时,它可以被缓存.所以你可以通过使它看起来依赖于输入来解决这个问题.在解释模式下,GHC对此并不十分聪明,因此很容易欺骗它:

main = do
    n <- return (10^10)
    putStrLn . show . doubleEachElement $ [1..n]

getList如果getList使用参数而不是硬编码,这也适用于您10^10.

幸运的是,在编译模式下,GHC对这些顶级符号的使用看起来更加困难,因此可以看到该列表仅使用一次,因此可以在输出时开始垃圾收集.

这个问题在现实世界中并不常见,因为程序通常很大程度上依赖于它们的输入,所以没有像这样的顶级大常量.但是,当GHC试图缓存你不想要它的东西时,这可能是一种痛苦.