使用Haskell中的List构造计算fib - 速度差异

Question

如果我们定义了以下内容:

lazyFib x y = x:(lazyFib y (x + y))
fib = lazyFib 1 1

(7周内7种语言的书).为什么

fibNth x = head (drop (x-1) fib)

评价慢于

fibNth2 x = head (drop (x-1) (take (x) fib)

？显然,第二个会在需要时立即终止无限列表 - 但直觉上我预期(头)调用在一个项目通过"丢弃"时终止评估,无论是否存在对fib的限制？谁能解释一下？

(更新时间参考):

> :set +s
> fibNth 100000
259740693472217241661550340212759154148804853865176...
(1.16 secs, 458202824 bytes)
> fibNth2 100000
259740693472217241661550340212759154148804853865176....
(0.09 secs, 12516292 bytes)

Answer 1

如果你翻转源文件或解释器中两个函数的顺序,你会发现第二个函数要快得多.

原因？fib是仅评估一次的顶级值.在第一次通话时,您可以根据需要对其进行评估,在第二次通话时,您只需轻轻一按即可.

您可以查看此SO问题,了解何时可以预期此类评估行为.简而言之,具有非多态类型的值是memoized,而多态值和函数应用程序则不是.