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.
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
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. :)