Рассуждение лени - программирование

У меня есть следующий фрагмент:

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

Я вижу это так: ничего не делается до печати. При печати разрывы разворачиваются с помощью первой распаковки, а затем сопоставляются сIntegral один Word8 за раз. Каждое из этих слов8 зашифровывается с 1, снова по одному значению за раз. Затем эти кортежи выполняются функцией аккумулятора, которая обновляет массив, по одному кортежу /Word 8 за раз. Затем мы переходим к следующему thunk и повторяем, пока не останется больше содержимого.

Это позволит создавать гистограммы в постоянной памяти, но, увы, этого не происходит, но вместо этого происходит сбой при переполнении стека. Если я попытаюсь профилировать его, я вижу, что он работает до конца, но занимает много памяти (300-500 МБ для файла 2,5 МБ). Память получается линейно до конца, пока она не будет отпущена, образуя "хороший" треугольный график.

Где мои рассуждения ошибочны и какие шаги я должен предпринять, чтобы сделать этот запуск в постоянной памяти?

Ответ 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 с вашим примером в качестве варианта использования.