haskell - 如何控制列表的每个元素加倍示例的惰性

Question

我试图解决Duplicate each element in a Haskell List任务并将其作为一个完整的程序，将列表写入标准输出

这是我的解决方案

main :: IO ()main = getList >>= return . doubleEachItem >>= putStrLn . showgetList = return [1,3,5]doubleEachItem :: [Int] -> [Int]doubleEachItem = foldr (++) [] . map (take 2 . repeat)

但是当我尝试处理很长的列表时

getList = return . take 10000000000 $ repeat 15

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

问题是:如何改进程序，使其能够处理任何大小的列表？

编辑:

我认为程序崩溃是因为我使用 runghc 命令运行它。在那种情况下，ghc 消耗大约 3GB 的内存并被操作系统杀死。崩溃后的输出文件只有大约 0.6GBytes。我不清楚这种行为的原因。

当我将程序编译为 native 可执行文件 ghc haskell03.hs -o haskell03 并通过重定向到文件 ./haskell03 >out03.txt 执行它时，它完美运行在恒定的内存空间中并以大约 20MBytes/秒的速度生成输出文件。程序完成后，输出文件占用 57GBytes。总执行时间为 47 分钟。

Answer 1

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

runghc 以解释模式运行，就好像您已经通过 ghci 加载了运行文件一样。 getList 是一个顶级绑定(bind)，因此它的值(以及它引用的所有值)都被缓存了。这意味着 GHC 试图缓存你的整个 100 亿元素数组。

您可能会认为，如果您将列表内联，它会起作用:

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

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

一般规则是，当某些内容不依赖于输入时，它可以被缓存。因此，您可以通过使其看起来取决于输入来解决此问题。在解释模式下，GHC 对此不是很聪明，所以很容易欺骗它:

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

这也适用于您的 getList，如果 getList 采用参数而不是硬编码 10^10。

幸运的是，在编译模式下，GHC 会更仔细地查看这些顶级符号的用法，因此它可以看到该列表只使用了一次，因此可以在输出时开始对其头部进行垃圾收集。

这个问题在现实世界中并不经常出现，因为程序经常严重依赖它们的输入，所以没有像这样的顶级大常量。但是，是的，当 GHC 尝试缓存您不想要的东西时，这可能会很痛苦。