p14.hs

-- project Euler problem 14
import Data.Array (Array,(!),listArray,assocs)
import Data.List  (foldl1',unfoldr)
import Data.Tuple (swap)
type Val = Int -- you might want to use Integer, not Int, for 32bit runtime
collatzLengths :: Int -> Array Int Val
collatzLengths nmax = arr
  where arr = listArray (1,nmax) (1:[cL i| i<-[2..nmax]])
        cL n = f n 0
          where f i c
                  | i < n     = (arr!i) + c
                  | even i    = f (i`div`2) (c+1)
                  | otherwise = f (3*i + 1) (c+1)
p14  = foldl1' max . map swap . assocs . collatzLengths 
main = print $ p14 1000000

-- for validation
collatz = unfoldr (\i -> if i<1 then Nothing else Just(i, next i))
  where next i | i==1 = 0 | even i = i`div`2 | otherwise = 3*i+1