Problem 14 その3

http://projecteuler.net/index.php?section=problems&id=14

コラッツ予想。1〜1,000,000 の数の中で1に収束するまでの遷移数が一番多い数は?

配列版。リストより効率がよい。

import List
import Array

n = 1 * 1000 * 1000 - 1

main = print $ maximumBy (\(_, a) (_, b) -> a `compare` b) $ assocs $ collatz n

collatz n = memoCollatz
    where memoCollatz = listArray (1, n) $ 1 : [1 + (f i) | i <- [2..n]]
              where f i = let i' = if even i then i `div` 2 else 3 * i + 1 in
                               if i' <= n
                                  then memoCollatz ! i'
                                  else 1 + f i'

27.05s user 0.39s system 99% cpu 27.696 total
速いな。

配列の ! はリストの !! と違って、Int じゃなく、Ix のインスタンスで構わない。
桁溢れを気にしなくてよくなったのかな。