为什么我需要为WriterT State提供这么多内存？

Question

试图掌握我试图使用WriterT和State（它是advent of code day 15）解决Haskell练习的概念。出于某种原因，我不明白我最终使用了大量的内存而我的笔记本（只有4G Ram）就停止了。

我的第一个想法是使用严格并洒上刘海 - 但问题仍然存在。

有人能解释我哪里出错了吗？

这是清理过的代码：

{-# LANGUAGE BangPatterns #-}
module Main where
import Control.Monad.State.Strict
import Control.Monad.Writer.Strict

main = do
  let generators = (Generator 65 16807, Generator 8921 48271)
      res1 = compute generators (4*10^7) 
  putStrLn "Answer 1"
  print res1

data Generator = Generator { _value :: Int
                           , _factor :: Int
                           }
    deriving Show

newtype Value = Value Int
  deriving (Show, Eq)

newtype Counter = Counter Int
  deriving (Show, Eq)

instance Monoid Counter where
  mempty = Counter 0
  mappend (Counter !a) (Counter !b) = Counter (a+b)

generate :: Generator -> (Value, Generator)
generate (Generator v f) = (Value newval, Generator newval f)
  where newval = (v * f) `mod` 2147483647

agree (Value a) (Value b) = (a `mod` mf) == (b `mod` mf)
  where mf = 2^16

oneComp :: State (Generator, Generator) Bool
oneComp = do
  (!ga, !gb) <- get
  let (va, gan) = generate ga
      (vb, gbn) = generate gb
      !ag = agree va vb
  put (gan, gbn)
  pure ag

counterStep :: WriterT Counter (State (Generator, Generator)) ()
counterStep = do
  !ag <- lift oneComp
  when ag $ tell (Counter 1)

afterN :: Int -> WriterT Counter (State (Generator, Generator)) ()
afterN n = replicateM_ n counterStep

compute s0 n = evalState (execWriterT (afterN n)) s0

我用堆栈编译它。 cabal文件中的条目是：

executable day15
  hs-source-dirs:      app
  main-is:             day15.hs
  ghc-options:         -threaded -rtsopts -with-rtsopts=-N 
  build-depends:       base
                     , advent
                     , hspec
                     , mtl
  default-language:    Haskell2010

更新

我有更多的时间，并遵循建议使发电机严格。然而，仍然有一些东西使用太多的记忆。

这是我认为可能相关的教程文件的一部分。

            Fri Dec 15 16:28 2017 Time and Allocation Profiling Report  (Final)

       day15 +RTS -N -p -RTS

    total time  =       71.66 secs   (71662 ticks @ 1000 us, 1 processor)
    total alloc = 17,600,423,088 bytes  (excludes profiling overheads)

COST CENTRE    MODULE    SRC                          %time %alloc

afterN         Main      app/day15.hs:79:1-36          41.1   20.0
mappend        Main      app/day15.hs:51:3-51          31.0    3.6
oneComp        Main      app/day15.hs:(64,1)-(71,9)     9.2   49.1
generate.(...) Main      app/day15.hs:55:9-42           8.5   14.5

Answer 1

原因很可能是WriterT层。

即使是“严格”的WriterT在累加器中也是完全懒惰的 - 在另一种意义上，它与累加器无关。

例如，该程序运行没有错误：

import Data.Monoid
import Control.Monad.Trans.Writer
import Control.Exception

main :: IO ()
main = do
  let (x,_) = runWriter $ do
        tell $ Sum (1::Float)
        tell (throw $ AssertionFailed "oops")
        tell (error "oops")
        tell undefined
        tell (let z = z in z)
        return True
  print x

此外，不可能从WriterT中“累积”累加器，因为没有办法达到它。

对于长计算，thunk会累积并消耗大量内存。

一种解决方案是将计数器存储在StateT层中。严格的modify'功能在这里很有用。

---

使用StateT作为仅附加累加器虽然有点令人不满意。另一个选择是使用Accum明智地定位BangPatterns。该程序抛出一个错误：

import Control.Monad.Trans.Accum

main :: IO ()
main = do
  let (x,_) = flip runAccum mempty $ do
        add $ Sum (1::Float)
        add $ error "oops"
        !_ <- look
        return True
  print x

Accum就像一个Writer，可以让你访问累加器。它不允许您随意更改它，只添加它。但是掌握它足以引入严格性。