推理懒惰

Question

我有以下代码片段：

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

我是这样看的:在打印之前什么都不做。在打印时，首先解开包装，然后一次映射一个fromIntegral，从而展开Word8。这些单词8中的每一个都是用1压缩的，同样是一次一个值。这些元组随后被累加器函数获取，该函数一次更新一个元组/字8。然后我们转到下一个thunk并重复，直到没有更多的内容。

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

我的推理在哪里出错了，我应该采取什么步骤让它在常量内存中运行？

Answer 1

我认为问题在于Data.Vector在其元素上并不严格。因此，尽管你的推理是正确的，但当你累积直方图时，你的大腿看起来像是：

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

而不是

<3 2 0 0 4 ...>

只有在打印时才会计算出这些总和。我在文档中没有看到严格的accum函数(可惜)，在seq中也没有任何地方可以挂接。摆脱这种困境的一种方法可能是使用Data.Vector.Unboxed，因为未装箱的类型是未被解除的，也就是严格的。也许你可以用你的例子作为用例来请求一个严格的accum函数。