Haskell如何立即计算这个巨大的数字？

Question

我开始学习Haskell,当我学习一门新语言时,我喜欢做的一件事就是将Project Euler问题作为我主要参考资料的补充.

我找到了第二个问题的解决方案,即找到偶数斐波纳契数不到四百万的总和:

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倍),并没有那么多的斐波纳契数小于40000000000000000000000000000000,可能不到100.

添加少于100个这个大小的数字(不是特别大)的计算机应该花费几微秒.

我不确定你的其他实现是什么样的,但是一个常见的错误就是像这样编写Fibonacci函数:

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)是在做什么,但上面的代码有点混乱,但也可能更容易翻译成其他语言.