Problem 14 （その3：答えはでた）

なぜスタックがあふれるのか．答えは自明で何でも溜め込むからなんですよね．1000000までの各整数に対してコラッツ列の長さを求めて，最大のものを求めると1000000個の要素のリストを扱わないといけないのは当たり前で，当然あふれても仕方がないです．

キャッシュにしても同様．溜め込む量が多くなるとヒットする確率もあがりますが，無駄な記録も増えるし探す手間もかかります．ヒットしないものを溜め込まないように細工するにも，その細工そのものが手間になったら意味がないです．

ということで，まずはキャッシュせず，しかも各整数ごとにそれ以前の「コラッツ列の最大長」と比較することで，最大長を計算します．

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

type Result = (Int, [Integer])

cfold::(Integer -> Result -> Result) -> Result -> [Integer] -> Result
cfold _ re     []     = re
cfold f (l,rs) (n:ns) =  seq x $ cfold f x ns
    where x = f n (l,rs)

-- コラッツ列を求める
collatz::Integer -> [Integer]
collatz n
    | n == 1    = [1]
    | otherwise = n:((collatz.next) n)
      where next:: Integer->Integer
            next n 
                | n `mod` 2 == 0 = n `div` 2
                | otherwise      = 3*n+1

{-
整数nとそれまでの結果(l,rs)を与えて
(1) n に対するコラッツ列を求める
(2) (1)の列の長さl(n)を求める
(3) lとl(n)を比較して
(3a) l=l(n)ならば(l,n:rs)を返す
(3b) l<l(n)ならば(l(n),[n])を返す
(3c) l>l(n)ならば(l,rs)を返す
-}
process::Integer -> Result -> Result
process n (l,rs)
    | l == ln = (l,n:rs)
    | l <  ln = (ln,[n])
    | l >  ln = (l,rs)
    where ln = length $ collatz n


answer::Integer -> Result
answer n = cfold process (1,[1]) [1..n]

1000000まで計算するのに約20分，837799が長さ525でこれが最大です．