Solution to Euler Problem 14 using memoization via a lazy array

CollatzLength.hs

-- inspired by: http://scrollingtext.org/project-euler-problem-14
-- executing main takes 5   sec in ghci
--                      0.7 sec when compiled with -O

import qualified Data.Vector as V

n :: Integer
n = 1000000

cacheSize :: Int
cacheSize = fromInteger $ 3 * n

collatzCache :: V.Vector Int
collatzCache = V.generate cacheSize (collatzLength . fromIntegral)

-- | PRE: 0 <= i
cachedCollatzLength :: Integer -> Int
cachedCollatzLength i
  | i <= n    = collatzCache V.! fromInteger i
  | otherwise = collatzLength i

collatzLength
  :: Integer  -- ^ The starting point of the Collatz path whose length
              -- we want to compute. We use an 'Integer' to make sure that no
              -- overflow happens for intermediate values.
  -> Int      -- ^ The length of the resulting Collatz path.
collatzLength i
  | i <= 1    = 0
  | otherwise = case i `quotRem` 2 of
      (i', 0) -> 1 + cachedCollatzLength i'
      _       -> 1 + cachedCollatzLength (3 * i + 1)

main :: IO ()
main = putStrLn $
    "maximum length of a Collatz chain below " ++ show n ++ ": " ++
    show (collatzCache V.! maxIdx) ++ " starting from " ++ show maxIdx
  where
    maxIdx = V.maxIndex $ V.take (fromInteger n + 1) collatzCache