haskell - Haskell 如何立即计算出这个庞大的数字？

Question

我开始学习 Haskell，当我学习一门新语言时，我喜欢做的一件事就是做 Project Euler 问题，作为我主要引用资料的补充。

对于第二个问题，找到小于 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 只是在胡编乱造？

Answer 1

它可能与 Haskell 无关，但与您用于其他解决方案的算法无关。

由于斐波那契数增长得相当快(平均每一步增加 1.6 倍)，小于 4000000000000000000000000000000 的斐波那契数并不多，可能不到 100。

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

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

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

这很糟糕，因为 fib n 调用 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) 正在做的事情，但是上面的代码有点困惑，但可能也更容易翻译成其他语言。