I’ve been learning Haskell on and off for couple of months now and part of the things I do when learning new language is to implement some programming problems on it so see how it feels.

So i was trying to solve this https://projecteuler.net/problem=2 which says:

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 initial solution was:

fib :: (Num a, Eq a) => a -> a -> [a]
fib a b = a : fib b (a + b)

findFibSum :: Integral a => [a] -> a -> a
findFibSum xs limit =
  sum [x | x <- xs, mod x 2 == 0 && x < limit]

The problem is that when I ran it appears to be stuck forever, I was thinking that after x hits the limit it would terminate the list and return the sum, but nothing is happening.

I can use take to get a batch of sequence and continue to do so until one of the item satisfies 4m but it feels hacky:

findFibSum (take 100 $ fib 1 2) 4000000

This will work since sequence no. 32 is 3524578 which is the last item < 4m and we get 100. See it doesn’t look precise, we need something better.

With my limited Haskell knowledge I asked on SO, it turns out the fibonacci sequence will just continue even if it doens’t satisy the limit anymore, it’ll just be a false everytime onwards but its still running.

The solution was to do the 4m checking right upon retrieving an item so we only get the sequence containing a max which is still < 4m.

findFibSum :: Integral a => [a] -> a -> a
findFibSum xs limit =
  sum [x | x <- takeWhile (<limit) xs, mod x 2 == 0]

The important thing here is takeWhile which stops taking from the sequence as soon as it fails to satify limit, then we have a precise list of items which has the max < 4m. So if you run this you’ll get:

*Main> findFibSum (fib 1 2) 4000000
4613732

So much for a fibonacci sequence. :)