haskell - 推理懒惰

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

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

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

我的推理哪里出了问题，我应该采取什么步骤才能使其在恒定内存中运行？

Answer 1

我认为问题在于 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 来代替，因为未装箱的类型是未解除的，也称为严格类型。也许您可以以您的示例作为用例来请求严格的 Accum 函数。