haskell - 推理懒惰

我有以下片段:

import qualified Data.Vector as V
import qualified Data.ByteString.Lazy as BL
import System.Environment
import Data.Word
import qualified Data.List.Stream as S

histogram ::  [Word8] -> V.Vector Int
histogram c = V.accum (+) (V.replicate 256 0) $ S.zip (map fromIntegral c) (S.repeat 1)

mkHistogram file = do
  hist <- (histogram . BL.unpack) `fmap` BL.readFile file
  print hist

我是这样看的:打印之前什么都不做。打印 thunk 时，先解包，然后从一个 Word8 一次映射一次。这些 word8 中的每一个都用 1 压缩，一次一个值。这个元组然后由累加器函数获取，该函数更新数组，一次一个元组/Word8。然后我们移动到下一个 thunk 并重复直到没有更多的内容。

这将允许在常量内存中创建直方图，但可惜这并没有发生，反而会因堆栈溢出而崩溃。如果我尝试对其进行概要分析，我会看到它一直运行到最后，但是占用了大量内存(2.5 Mb 的文件需要 300-500 Mb)。内存是线性获取的，直到最后可以释放，形成一个“漂亮”的三角图。

我的推理哪里出错了，我应该采取什么步骤来使这个在恒定内存中运行？

最佳答案

我认为问题在于 Data.Vector 的元素并不严格。因此，尽管您的推理是正确的，但在累积直方图时，您的 thunk 看起来像:

<1+(1+(1+0)) (1+(1+0)) 0 0 (1+(1+(1+(1+0)))) ... >

而不是

<3 2 0 0 4 ...>

并且只有在您打印时才会计算这些总和。我在文档中没有看到严格的 accum 函数(耻辱)，并且没有任何地方可以 Hook seq 。摆脱这种困境的一种方法可能是改用 Data.Vector.Unboxed，因为未装箱的类型是 unlifted aka strict。也许您可以以您的示例作为用例请求严格的 accum 函数。

关于haskell - 推理懒惰，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5274700/