Problem 167

http://projecteuler.net/index.php?section=problems&id=167
偶数項が２つしかあらわれない、という事実を利用。
循環を考える。
メモリが足りなくなったので、STを利用。
しかし、まぁ、コードがきれいじゃないですね。
しかも、結局

$ ./p167.exe
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.

と出力されてしまう。
これは何がいけないのか？
よく分からない。まぁ、解けたからよしとしよう。

import Data.STRef (STRef,newSTRef,readSTRef,modifySTRef)
import Control.Monad.ST (ST,runST)
import Control.Monad (liftM2,zipWithM_)

next :: STRef s [Bool] -> STRef s Int -> STRef s Int -> ST s ()
next bs p d = do modifySTRef d (+2)
                 bs' <- readSTRef bs
                 if head bs'
                    then modifySTRef p (+1) >> (modifySTRef bs.append $ not.last $ bs')
                    else modifySTRef bs.append $ last bs'
    where append b = (b:).init

period :: Int -> STRef s [Bool] -> STRef s Int -> STRef s Int -> ST s (Int,Int)
period n bs p d = do bs' <- readSTRef bs
                     if bs' == replicate n False ++ [True]
                        then liftM2 (,) (readSTRef p) (readSTRef d)
                        else next bs p d >> period n bs p d

value :: Int -> Int -> STRef s [Bool] -> STRef s Int -> STRef s Int -> ST s (Int)
value k n bs p d = do p' <- readSTRef p
                      if p' == k
                         then readSTRef d
                         else next bs p d >> value k n bs p d

largeValue :: Integer -> Int -> ST s Integer
largeValue k n = do bs <- newSTRef ini
                    [p,d] <- mapM newSTRef [0,2]
                    (pr,df) <- period n bs p d
                    let (q,r) = divMod (k-3) $ toInteger pr
                    modifySTRef bs (const ini)
                    zipWithM_ modifySTRef [p,d] [const 0,const $ n-2]
                    ur <- value (fromIntegral $ r+1) n bs p d
                    return $ toInteger ur + q * toInteger df
    where ini = True : replicate n False

main :: IO ()
main = print.sum.runST $ mapM (largeValue $ 10^11) [5,7..21]

[追記]

StateTとIORefを使ってみた。
遅くなった…
可読性は向上したのか？

import Data.IORef (IORef,newIORef,readIORef,modifyIORef)
import Control.Monad.State (StateT,evalStateT,lift,get)
import Control.Arrow (first,second,(***))

type Ref = IORef ([Bool],(Int,Int))

next :: StateT Ref IO ()
next = do ref <- get
          (bs,_) <- lift.readIORef $ ref
          lift.modifyIORef ref .second.second $ (+2)
          if head bs
             then lift.modifyIORef ref $ (append.not.last $ bs) *** first succ
             else lift.modifyIORef ref.first.append.last $ bs
    where append b = (b:).init

period :: Int -> StateT Ref IO (Int,Int)
period n = do (bs,(p,d)) <- get >>= lift.readIORef
              if bs == replicate n False ++ [True]
                 then return (p,d) else next >> period n

value :: Int -> Int -> StateT Ref IO Int
value k n = do (bs,(p,d)) <- get >>= lift.readIORef
               if p == k
                  then return d else next >> value k n

largeValue :: Integer -> Int ->  StateT Ref IO Integer
largeValue k n = do ref <- get
                    lift.modifyIORef ref.const $ (ini,(0,2))
                    (pr,df) <- period n
                    let (q,r) = divMod (k-3) $ toInteger pr
                    lift.modifyIORef ref.const $ (ini,(0,n-2))
                    ur <- value (fromIntegral $ r+1) n
                    return $ toInteger ur + q * toInteger df
    where ini = True : replicate n False

main :: IO ()
main = newIORef undefined >>= evalStateT (mapM (largeValue $ 10^11) [5,7..21]) >>= print.sum

いまいち、StateTのなかで、IORef,STRefの扱い方が分からない。
modifyとか使って更新したかったが、できなかった。
STRefを使用したやつ

import Data.STRef (STRef,newSTRef,readSTRef,modifySTRef)
import Control.Monad.State (StateT,evalStateT,lift,get)
import Control.Monad.ST
import Control.Arrow (first,second,(***))

type StateST s a = StateT (STRef s ([Bool],(Int,Int))) (ST s) a

next :: StateST s ()
next = do ref <- get
          (bs,_) <- lift.readSTRef $ ref
          lift.modifySTRef ref .second.second $ (+2)
          if head bs
             then lift.modifySTRef ref $ (append.not.last $ bs) *** first succ
             else lift.modifySTRef ref.first.append.last $ bs
    where append b = (b:).init

period :: Int -> StateST s (Int,Int)
period n = do (bs,(p,d)) <- get >>= lift.readSTRef
              if bs == replicate n False ++ [True]
                 then return (p,d) else next >> period n

value :: Int -> Int -> StateST s Int
value k n = do (bs,(p,d)) <- get >>= lift.readSTRef
               if p == k
                  then return d else next >> value k n

largeValue :: Integer -> Int ->  StateST s Integer
largeValue k n = do ref <- get
                    lift.modifySTRef ref.const $ (ini,(0,2))
                    (pr,df) <- period n
                    let (q,r) = divMod (k-3) $ toInteger pr
                    lift.modifySTRef ref.const $ (ini,(0,n-2))
                    ur <- value (fromIntegral $ r+1) n
                    return $ toInteger ur + q * toInteger df
    where ini = True : replicate n False

main :: IO ()
main = print.sum.runST $ newSTRef undefined >>= evalStateT (mapM (largeValue 100) [5,7..21])

StateT使ったらメモリがたりねぇ。