Haskell
ProjectEuler

Project EulerをHaskellで解いていく(Problem2: Even Fibonacci numbers)


TL;DR

Haskellの勉強を兼ねてProject Eulerを解いていきます。

始めたばかりでわからないことが多いのでコメント頂けると嬉しいです。


問題文


Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

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



コード

fib 0 = 0

fib 1 = 1
fib n = fib(n-1) + fib(n-2)

fibList n = takeWhile (<=n) [x | x <- map fib [0..]]
evenList list = filter even list
evenSumFib n = sum $ evenList $ fibList $ n

main::IO()
main = do
print $ evenSumFib 4000000

このコードで約5秒くらい処理時間がかかりました。

高速化するためにメモ化してみようと思いググりながらやって以下のfib関数ができましたが、 (map memo [0..] !!) の!! が理解できずに不採用にしました。

fib = (map memo [0..] !!)

where
memo 0 = 0
memo 1 = 1
memo n = fib(n-1) + fib(n-2)