Haskell 如何立即计算出如此巨大的数字？

我开始学习 Haskell，当我学习一门新语言时我喜欢做的事情之一就是欧拉计划 https://projecteuler.net/问题作为我主要参考资料的补充。

对于第二个问题，即查找小于 400 万的偶数斐波那契数之和，我提出了以下解决方案：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
f :: Integer -> Integer
f n =
  let evenFib = filter (\n -> n `mod` 2 == 0) fibs
  in sum (takeWhile (<n) evenFib)

这很好用；f 4000000返回正确答案。它立即就会这样做。出于好奇，我开始输入越来越大的数字......

Prelude> f 40000000
19544084
Prelude> f 400000000000
478361013020
Prelude> f 40000000000000000000000000000000
13049874051046942401006156573274
Prelude> f 2370498572349582734598273495872349587234958723948752394857
2805750129675962215536656398462489370528480907433875715844

这些值中的每一个都会立即返回。我无法保证最后两个答案的准确性，因为我在其他语言中的实现不适用于这么大的数字。

所以，我的问题是，Haskell 在这里做什么？它如何立即返回这些值（无论它们实际上是否正确）？此外，这些答案确实正确吗，还是 Haskell 只是编造的东西？

这可能与 Haskell 特别无关，而是与您用于其他解决方案的算法有关。

由于斐波那契数增长得相当快（平均每一步增长 1.6 倍），所以没有那么多斐波那契数小于 40000000000000000000000000000000，可能少于 100。

计算机添加少于 100 个这样大小的数字（不是特别大）应该需要几微秒。

我不确定你的其他实现是什么样的，但一个常见的错误是像这样编写斐波那契函数：

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

这太可怕了，因为fib n calls fib (n-1)，然后调用fib (n-2)，并将答案返回fib n。但接下来你必须去计算一下fib (n-2)再次因为您尚未保存答案。

更好地实施fib在 Haskell（或者任何其他语言）中，如下所示：

fib 0 = 0
fib n = fib' 0 1 n

fib' _ curr 1 = curr
fib' last curr n = fib' curr (last+curr) (n-1)

请注意，每个fib'调用仅使一次递归全部，而不是两次。我上面写的大概是这样的0 : 1 : zipWith (+) fibs (tail fibs)正在做，但是上面的代码有点混乱，但可能也更容易翻译成其他语言。