takafumi blog

日々の勉強メモ

【Haskell】 Project Euler Prblem2を読み間違えて解いてみた

環境   ghc 7.10.2 CentOS7.0

Problem 2 - PukiWiki

「数列の項の値が400万以下の, 偶数値の項の総和を求めよ.」

「数列の項が400万以下の, 偶数値の項の総和を求めよ。」
と間違って解いてみた。

  1 main :: IO ()
  2 main = print . sum' .filter even $ take 4000000 fibonacci
  3
  4 fibonacci :: [Integer]
  5 fibonacci = 1:2:zipWith' (+) fibonacci (tail fibonacci)
  6
  7 zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
  8 zipWith' f (x:xs) (y:ys) = z `seq` z : zipWith' f xs ys
  9     where z = f x y
 10
 11 sum' :: [Integer] -> Integer
 12 sum' [] = 0
 13 sum' (x:[]) = x
 14 sum' (x1:x2:xs) = s `seq` (sum' (s:xs))
 15     where s = x1 + x2

駄目でした。

$ runghc problem2.hs
<interactive>: out of memory (requested 1048576 bytes)

zipWithとsumが正格ならいけるか?
と思ったんですが、ghc使用可能メモリを計算結果だけで突破した模様。

という事で、正しい問題で解いて終りにした。

1 main :: IO ()
2 main = print . sum' .filter even $ takeWhile (< 4000000) fibonacci