haskell - Project Euler 2：Haskell 实现混乱

Question

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

我将无限列表 fibs 定义为：

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

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

前奏> [x | x<-fibs, x mod2 == 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
前奏>总和$[x| x <- [1..], x mod2 == 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 编译器在一般情况下无法知道理解表达式是否表示有限列表；问题是不确定的。

Answer 2

它也挂在第一个命令上，不是吗？:)

带有test的列表推导等效于filter表达式，而不是takeWhile表达式：

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

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

这清楚地描述了非终止计算。

Haskell 推导式没有 Prolog 的削减（即“！”）等价物。在 Prolog 中，我们能够“从测试中”停止计算：

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

但在 Haskell 中，我们必须使用takeWhile, 或来模拟剪切take。

Answer 3

替换[1..]为fibs，您的第二个变体将等同于第一个变体。

编辑：哦，对不起，它不会。但这将是“更少”的错误：）我应该更加注意......</p>