# Haskell: Project Euler problem 2

by on January 12, 2012

Today’s post features the second problem of Project Euler involving the famous Fibonacci numbers.

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.

My first attempt used a straight-forward implementation of a single fibonacci number and calculating each one less than four million separately:

``````fibonacci :: Int -> Int
fibonacci 1 = 1
fibonacci 2 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)

solution :: Int
solution =
sum \$ filter even \$ takeWhile (<4000000) [fibonacci x | x <- [1..]]``````

Since this solution runs not very efficently I tried to come up with a slightly improved version:

``````fibSeq :: Int -> [Int]
fibSeq 1 = 
fibSeq 2 = [1, 1]
fibSeq n = fibSeq' n [1,1]

fibSeq' :: Int -> [Int] -> [Int]
fibSeq' n list@(x:y:_) =
if next > n then
list
else
fibSeq' n (next:list)
where
next = x + y

solution2 :: Int
solution2 =
sum \$ filter even \$ fibSeq 4000000``````

Now after reviewing the written code I notice that it is easily possible to rewrite the `fibSeq'` function using guards. The resulting function looks more readable to me:

``````fibSeq' :: Int -> [Int] -> [Int]
fibSeq' n list@(x:y:_)
| next > n = list
| otherwise = fibSeq' n (next:list)
where
next = x + y``````

This post is tagged with euler, haskell and programming