Project Euler 解答

Project Euler Problem 002

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]]

since 2013