Project Euler 2: Haskell implementation confusion
haskell
Solution
When evaluating
[x | x<-fibs, x mod 2 == 0, x<4000000]
your program/the Haskell compiler does not know that this list is actually finite. When you call a function that consumes a list entirely such as `sum`, it just keeps generating Fibonacci numbers, testing them for `x<4000000` (and failing every time after a certain point).
In fact, the Haskell compiler cannot know in the general case whether a comprehension expression denotes a finite list; the problem is undecidable.
Problem
I am using GHCi to try to solve problem 2 on Project Euler. http://projecteuler.net/problem=2 I defined the infinite list fibs as: Prelude> let fibs = 1 : 2 : zipWith(+) fibs (tail fibs) I tried using list comprehensions in the following manner: Prelude> [x | x<-fibs, x `mod` 2 == 0, x<4000000] [1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578 Prelude> sum $ [x | x <- [1..], x `mod` 2 == 0, x<4000000] But the shell hangs on the second command. I am confused as to why the list comprehension can build the list but the sum function cannot process it. I found that a working solution is Prelude> sum $ filter even $ takeWhile (<= 4000000) fibs But once again I am confused as to why that works when the list comprehension method doesn't.