Project Euler 2: Haskell implementation confusion

3
votes

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.

3
haskell
The list comprehension method works fine if you constrain fibs: [x | x <- takeWhile (< 4000000) fibs , mod x 2 == 0] – applicative
I think you're being a bit disingenuous here: the first command hangs the shell, too! So it didn't build the list after all. You can see this in your output, too; there's no closing ]. – Daniel Wagner
btw the first command has a syntax error and doesn't run at all (it should be `mod` in backticks, or mod x 2), and once fixed it should only output even numbers ... – Vincent Beffara

3 Answers

14
votes

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.

1
votes

it hangs on the first command as well, isn't it? :)

a list comprehension with test is equivalent to a filter expression, not a takeWhile expression: 

sum $ [x | x <- [1..], x mod 2 == 0, x<4000000] ===

sum $ filter (<4000000) $ filter even $ [1..]

this clearly describes a non-terminating computation.

Haskell comprehensions have no Prolog's cut (i.e. "!") equivalent. In Prolog, we are able to stop a computation "from within the test":

sum(I,Acc,Res):- I >= 4000000, !, Res = Acc ;
  Acc2 is Acc+I, sum(I+1,Acc2,Res).

but in Haskell we must emulate the cut by using takeWhile, or take.

0
votes

Replace [1..] with fibs, and your second variant will be equivalent to the first.

EDIT: oh sorry, it won’t. But it will be “less” wrong :) I should be paying more attention…