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 [,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 ,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,(,2))
(pr,df) <- period n
let (q,r) = divMod (k-3) $ toInteger pr
lift.modifyIORef ref.const $ (ini,(,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,(,2))
(pr,df) <- period n
let (q,r) = divMod (k-3) $ toInteger pr
lift.modifySTRef ref.const $ (ini,(,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使ったらメモリがたりねぇ。