Collatz.hs

-- SPOILER for project euler #14


-- Really, you should go do it yourself.




































import Data.List
import Data.Function
import Numeric
import Data.Char (intToDigit)

data Tree = Tree {value :: Int,
                  branch0 :: Tree,
                  branch1 :: Tree}

collatzLength :: Int -> Int
collatzLength = collatzLength' where
  collatzLength' 1 = 1
  collatzLength' n | n `mod` 2 == 0 = 1 + lookupInCAF (n `div` 2)
  collatzLength' n = 1 + lookupInCAF (3*n + 1)
  lookupInCAF n =
    lookupBinary (tail $ showIntAtBase 2 intToDigit n "") collatzCAF'
  lookupBinary "" t = value t
  lookupBinary ('0':x) t = lookupBinary x (branch0 t)
  lookupBinary ('1':x) t = lookupBinary x (branch1 t)
  lookupBinary _ _ = error "Not just 0 and 1"
  collatzCAF' = mkTree 1
  mkTree n = Tree (collatzLength' n) (mkTree (2*n)) (mkTree (1 + 2*n))

main :: IO ()
main = do
  let collatzMax = maximumBy (compare `on` collatzLength) [1..999999]
  print collatzMax
  print $ collatzLength collatzMax