haskell - 欧拉项目 2 : Haskell implementation confusion

Question

我正在使用 GHCi 尝试解决 Project Euler 上的问题 2。
http://projecteuler.net/problem=2

我将无限列表 fibs 定义为:

Prelude> let fibs = 1 : 2 : zipWith(+) fibs (tail fibs)

我尝试以下列方式使用列表推导式:

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]

但是 shell 卡在第二个命令上。我很困惑为什么列表理解可以构建列表但 sum 函数无法处理它。

我发现一个有效的解决方案是

Prelude> sum $ filter even $ takeWhile (<= 4000000) fibs

但是，当列表理解方法不起作用时，我又一次对为什么它起作用感到困惑。

Answer 1

评估时

[x | x<-fibs, x mod 2 == 0, x<4000000]

你的程序/Haskell 编译器不知道这个列表实际上是有限的。当您调用一个完全使用列表的函数时，例如 sum ，它只是不断地生成斐波那契数，测试 x<4000000 (并且每次都在某个点之后失败)。

实际上，Haskell 编译器在一般情况下无法知道推导式表达式是否表示有限列表；问题是 undecidable .