Project Euler Problem 14（その4）

コラッツ問題でなんとか答えはでていますが，せっかくStateモナドを頑張ったので，それで書いてみます．

StateモナドがMonadFixのインスタンスだとかは・・・スルーします．

import Control.Monad.State
import Data.List

{-
Project Euler Problem 14 e14-8.hs
-}

type Cache = [(Integer, Integer)] -- 整数とそれに対するコラッツ列の長さ

-- コラッツ列を求める
collatz::Integer -> State Cache Integer
collatz 1  = return 1
collatz n  = do cache <- get
                case (lookup n cache) of
                    Just k  -> return k
                    Nothing -> do num <-if n `mod` 2 ==0 then  collatz (n `div` 2) 
                                                         else  collatz (3*n+1)
                                  cache <- get
                                  put ((n,num+1):cache)
                                  return (num+1)


f xs n= execState (collatz  n) xs

g n = foldl f [] [1..n]

g 10などとすると，1から10までに対する「コラッツの列」の長さと，その途中計算で出てくる数とそのコラッツの列の長さがタプルででてきます．例えば

 g 10

[(9,20),(28,19),(14,18),(7,17),(22,16),(11,15),(34,14),(17,13),(52,12),(26,11),(13,10),(40,9),(20,8),(6,9),(3,8),(10,7),(5,6),(16,5),(8,4),(4,3),(2,2)]

となります．途中経過も含めてひたすら溜め込みますので，その点では非効率ですが，それなりに動きます．この結果を加工すれば，「長さ最大のコラッツ列」を求めることは容易でしょう．

残念ながら，この溜め込み方だとstack over flowがでてきて1,000,000は計算できません．溜め込むものを適宜カットする必要があります．