module Fib where
-- | To find more version how to calculate the Fibonacci sequence, have a look
--   at <http://www.haskell.org/haskellwiki/The_Fibonacci_sequence>

import Data.List

-- | The algorithms to test

fib1 :: Int -> Int
fib1 n = {-# SCC "fib1" #-} 
  let fibs = (0 : 1 : zipWith (+) (fibs) (tail fibs)) in fibs !! n

fib2 :: Int -> Int 
fib2 n = {-# SCC "fib2" #-}
    snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n
    where
        unfoldl f x = case f x of
                Nothing     -> []
                Just (u, v) -> unfoldl f v ++ [u]
 
        divs 0 = Nothing
        divs k = Just (uncurry (flip (,)) (k `divMod` 2))
 
        fib' (f, g) p
            | p         = (f*(f+2*g), f^2 + g^2)
            | otherwise = (f^2+g^2,   g*(2*f-g))