Невозможно заставить строгость в хвостовой рекурсии

Question

Я имею дело с утечками памяти в моей программе на Haskell, и мне удалось изолировать ее от очень простой проблемы лени при работе с массивами. Я понимаю, что там происходит. Первый элемент массива вычисляется, а остальные производят отложенные вычисления, которые потребляют кучу. К сожалению, я не смог навязать строгость для всего вычисления массива.

Я попробовал различные комбинации seq, BangPatterns ($!) Без особого успеха.

import Control.Monad

force x = x `seq` x

loop :: [Int] -> IO ()
loop x = do
  when (head x `mod` 10000000 == 0) $ print x
  let x' = force $ map (+1) x
  loop x'

main = loop $ replicate 200 1

Профиль со стандартными параметрами профилирования не дал мне больше информации, чем я уже знаю:

ghc -prof -fprof-auto-calls -rtsopts test.hs
./test +RTS -M300M -p -hc

Недостаточно памяти за несколько секунд.

Answer 1

force x = x `seq` x

Это бесполезно.seq не означает «оцените эту вещь сейчас»;это означает «оценить левую вещь, прежде чем возвращать результат оценки правильной вещи».Когда они одинаковые, это ничего не делает, а ваш force эквивалентен просто id.Попробуйте вместо этого:

import Control.DeepSeq
import Control.Monad

loop :: [Int] -> IO ()
loop x = do
  when (head x `mod` 10000000 == 0) $ print x
  let x' = map (+1) x
  loop $!! x'

main = loop $ replicate 200 1

Это оценивает x' и все, что в нем до loop x', что полезно.

В качестве альтернативы Control.DeepSeq имеет функцию force, котораяполезно.Его семантика в этом случае - «оценить все элементы вашего списка перед возвратом результата оценки любого из него».Если бы вы использовали его функцию force вместо своей, ваш исходный код работал бы иначе, так как первая строка loop оценивает начало списка.