推理懒惰

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时,然后一次从一个Word8映射.这些word8中的每一个都用1压缩,一次一个值.这个元组然后由累加器函数获取,该函数一次更新数组,一个元组/ Word8.然后我们移动到下一个thunk并重复直到不再有内容.

这将允许在常量内存中创建直方图,但是这不会发生,而是它会因堆栈溢出而崩溃.如果我尝试对其进行分析,我会看到它运行到最后,但是记忆很多(对于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在docs中看到严格的功能(羞耻),也没有任何地方可以挂钩seq.摆脱这种困境的一种方法可能是改为使用Data.Vector.Unboxed,因为未装箱的类型也是不受限制的.也许您可以将accum您的示例作为用例请求严格的函数.