ProjectEuler Q2: Haskell solution won't evaluate

2
votes

I invite you to check out the following fibonacci related problem from project Euler. The question asks the users to first generate a fibonacci sequence or function capable of returning the nth fibonacci number. I used the zipWith solution to generate a lazy/infinite list of fibonacci numbers:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Next, the question asks to restrict the list to fibonacci numbers/values less than 4e6, and then sum the even numbers. I thought this would be a very simple list comprehension:

sum [x | x<-fibs, even x && x < (4*10^6 + 1)]

This expression will not finish evaluating.... I thought it would proceed until it finds the right-most number (the first fib greater than 4e6, the 34th element in the list fibs!!34) and then terminate the list, summing a small number of integers. What am I doing wrong?

1
haskell
You can use takeWhile to stop processing the list when it no longer satisfies a predicate. – 4castle
The list is monotonic increasing, but haskell doesn't know this - so it won't stop evaluating elements from it just because you go over a threshold that's tied into a predicate in a list comprehension running over it. – hnefatl

1 Answers

6
votes

ghc doesn't know when [x | x<-fibs, even x && x < (4*10^6 + 1)] should terminate and it will try to exhaust the infinite list fibs. In otherwords, it will try to exhaust an infinte list of fibonacci numbers before termating. You should look into takeWhile.