这个Haskell代码会占用太多内存吗？

Question

如在此代码中:

import Data.Char
groupsOf _ [] = []
groupsOf n xs = 
    take n xs : groupsOf n ( tail xs )

problem_8 x = maximum . map product . groupsOf 5 $ x
main = do t <- readFile "p8.log" 
      let digits = map digitToInt $concat $ lines t
      print $ problem_8 digits

我意识到在Haskell中许多程序构造并且似乎存储了一些中间结果,例如groupsOf上面代码中的列表.以上代码是来自Haskell网站的 Euler项目问题​​8的参考答案.原始问题要求在一个非常长的数字链中连续5位数的最大乘积,例如45343231635723421312443535767983456.因此代码将计算所有产品并将其存储为列表.在其他语言中,我认为它们只会保留一个临时的最大值,并丢弃任何较小的值.

那么groupsOf真的存储了所有中间结果吗？如果问题扩大怎么办？它会分配太多内存吗？

Answer 1

不,不是因为groupsOf.那个只需要一次将一个组保留在内存中.然而,maximum可能会建立一个较大的thunk,因为它太懒惰,所以一定要要么编译-O或-O2使得进行严格的分析,或使用foldl1' max代替¹.

_{¹ foldl1'发现于Data.List}

Answer 2

我意识到在Haskell中许多程序构造并且似乎存储了一些中间结果,例如上面代码中的groupsOf列表.

"似乎"在这里说是一件好事,因为老实说,这就是Haskell能够真正发挥作用的地方.事实上,由于懒惰,它可以占用更少的内存,而不需要复杂的微观管理.

懒惰IO(例如readFile)的一个很好的事情是,它只会根据需要读取尽可能多的文件,并且在您使用其内容时可以对文件进行垃圾收集.(好吧,大致如此.这取决于你如何设置缓冲.)

这是一个关于如何执行程序的草图:

t <- readFile "p8.log"

为...创建一个thunk t :: String.可能检查文件是否存在,并以读取模式打开它.

 let digits = map digitToInt $concat $ lines t

为...创建一个thunk digits :: [Int]

 print $ problem_8 digits

一旦我们尝试执行此操作,所有工作将实际完成.我们需要进行全面评估problem_8 digits :: Int才能打印出来.所以我们创造了一个thunk problem_8 digits并强制它.

maximum . map product . groupsOf 5 $ digits

此时,maximum需要前两个元素map product . groupsOf 5 $ digits才能看出两者中哪一个更大.因此map product需要看到groupsOf 5 digits传递的前两个元素.

现在,groupsOf 5将需要前5个元素digits才能生成其第一个元素.此时,可能会读取文件的第一行,并完成定义的转换.groupsOf可以构造它的第一个元素,也可能是它的第二个元素(假设该行上有超过6个字符).groupsOf 5 digits将它的前两个元素传递给链,我们product将这两个元素映射到这两个元素,然后maximum检查两个元素中哪一个更大.我们保留结果,两者中较大的一个.

在这一点上(实际上比这一点早一点)我们可以完全抛弃中间结果.groupOf 5 digits现在完全不需要前两个要素; 我们永远不需要再次检查它们,垃圾收集器可以随时收集它们.该文件的前两个字符也将不再使用,并且可以被丢弃.

现在,这非常手动,可能有点不准确.但是你明白了吗？Haskell是惰性的(以及技术上Haskell是"不严格",这是通过懒惰普遍实行),这使得它的执行风格多少没有严格的语言不同.这使我们可以使用看似大量的中间表示和数据结构,而不会实际占用大量内存.好的编译器,比如GHC,可以像你不相信的那样优化内存使用.