Project Euler Problem 002

{-# LANGUAGE ParallelListComp #-}
import Control.Monad
fibl :: [Integer]
fibl = 0 : 1 : zipWith (+) fibl (tail fibl)
-- 4613732
main :: IO ()
main = print $ sum $ filter even $ takeWhile (< 4000000) fibl

-- ここ以下はいろいろなフィボナッチ
fibl2 :: [Integer]
fibl2 = 0 : 1 : next fibl2 where next (a: t@(b:_)) = (a+b) : next t
fibl3 :: [Integer]
fibl3 = 0:1:z(+) fibl3(tail fibl3) where
        z f (x:xs) (y:ys) = xy`seq` xy : z f xs ys where
          xy = x + y

fibslow :: (Num a, Num a1, Ord a) => a -> a1
fibslow n | n <=1 = 1
fibslow n = fibslow (n-1) + fibslow (n-2)

fibcpsslow :: (Ord a, Num a) => a -> (a -> t) -> t
fibcpsslow n c | n <= 1 = c 1
           | True   = 
             fibcpsslow (n-1) $ \x->
             fibcpsslow (n-2) $ \y->
             c (x + y)
  
fibp :: (Num a, Num b, Ord a) => a -> b
fibp n = fst (fibpair n)  
fibpair :: (Num a, Num t, Ord a) => a -> (t, t)
fibpair n | n <= 1 = (1,1)
          | True =
  let (n1,n2) = fibpair(n-1) in
  (n1+n2,n1)
  
fibonacci :: [Integer]
fibonacci = fibs 1 1 where fibs a b = a : fibs b (a + b)
                           
zip_fibs :: [Integer]
zip_fibs = 0 : 1 : [x+y | ~(x,y) <- zip zip_fibs (tail zip_fibs)]
zip_fib :: Int -> Integer
zip_fib = (!!) zip_fibs
memoized_fibs :: [Integer]
memoized_fibs = map memoized_fib [1..]
memoized_fib :: Int -> Integer
memoized_fib = ((map fib' [0 ..]) !!)
    where
      fib' 0 = 0
      fib' 1 = 1
      fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)
another_fibs :: [Integer]
another_fibs = 0 : 1 : 1 : map f [3..]
    where
      square x = x * x
      sqfib = square . another_fib
      f n | even n = sqfib (k+1) - sqfib (k-1) where k = n `div` 2
      f n          = sqfib k + sqfib (k-1) where k = (n + 1) `div` 2
another_fib :: Int -> Integer
another_fib = (!!) another_fibs

--scanl
fibscan :: [Integer]
fibscan = scanl1(+)(0:1:fibscan)
fibscan2 :: [Integer]
fibscan2= scanl(+)0(1:fibscan2)
--fixed fibscan
fix :: (t -> t) -> t
fix f = let g = f (fix f) in g  
fibfix :: [Integer]
fibfix = fix(scanl(+)0.(1:)) --これはインラインで使える

fibbb :: [Integer]
fibbb = 1:1:ap(zipWith(+)) tail fibbb

-- ParallelListComp拡張によるfib
-- zipWithのような動作をする
fibsp :: [Integer]
fibsp = 0 : 1 : [ a + b | a <- fibsp | b <- tail fibsp ]
-- 参考：ParallelListComp
plc :: [(Integer, Integer)]
plc = [(a,b)|a<-[1..]|b<-[5..10]]