斐波那契功能是通过什么机制记忆的？
fib = (map fib' [0..] !!)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)
与此相关的是，为什么没有这个版本？
fib n = (map fib' [0..] !! n)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)
最佳答案
Haskell中的评估机制是必需的:当需要一个值时，将对其进行计算，并在准备再次输入时保持就绪状态。如果我们定义一些列表xs=[0..]，然后再请求其第100个元素xs!!99，则列表中的第100个插槽将被“清除”，现在保留数字99，准备进行下一次访问。
这就是“遍历列表”的窍门。在正常的双递归Fibonacci定义fib n = fib (n-1) + fib (n-2)中，函数本身从顶部两次被调用，从而导致指数爆炸。但是有了这个技巧，我们为中期结果列出了一个 list ，然后“遍历 list ”:
fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]
诀窍是使该列表得以创建，并使该列表在调用
fib之间不消失(通过垃圾回收)。实现此目的的最简单方法是命名该列表。 “如果您命名，它将保留。” 您的第一个版本定义了一个单态常数，第二个版本定义了一个多态函数。多态函数无法针对可能需要使用的不同类型使用相同的内部列表，因此无法共享，即没有备注。
在第一个版本中，编译器对我们来说很慷慨，取出了该常量子表达式(
map fib' [0..])并使其成为一个单独的可共享实体，但是这样做没有任何义务。实际上，在某些情况下，我们不希望它自动为我们做到这一点。(编辑:)考虑以下重写:
fib1 = f fib2 n = f n fib3 n = f n
where where where
f i = xs !! i f i = xs !! i f i = xs !! i
xs = map fib' [0..] xs = map fib' [0..] xs = map fib' [0..]
fib' 1 = 1 fib' 1 = 1 fib' 1 = 1
fib' 2 = 1 fib' 2 = 1 fib' 2 = 1
fib' i=fib1(i-2)+fib1(i-1) fib' i=fib2(i-2)+fib2(i-1) fib' i=f(i-2)+f(i-1)
因此，真实的故事似乎与嵌套作用域定义有关。第一个定义没有外部作用域，第三个定义注意不要调用外部作用域
fib3，而是调用相同级别的f。每次对
fib2的新调用似乎都会重新创建其嵌套定义，因为根据n的值，可以在理论上对它们中的任何一个进行不同的定义(感谢Vitus和Tikhon指出了这一点)。在第一个定义中，没有n依赖，而在第三个定义中，没有依赖关系，但是对fib3的每个单独调用都调用f，这要小心，仅在此fib3特定调用内部的同级范围内调用定义，因此，对于xs的调用，相同的fib3被重用(即共享)。但是，没有什么可以阻止编译器认识到上述任何版本中的内部定义实际上都独立于外部
n绑定(bind)，因此毕竟可以执行lambda lifting，从而产生完整的备注(多态定义除外)。实际上，当使用单态类型声明并使用-O2标志进行编译时，这三个版本都会发生这种情况。使用多态类型声明，fib3表现出本地共享，而fib2则根本没有共享。最终，取决于编译器和所使用的编译器优化，以及如何对其进行测试(将文件加载到GHCI中，是否使用-O2进行编译或不进行编译，还是独立运行)，以及该行为是否为单态或多态类型，行为可能完全更改-无论是本地共享(每次通话)共享(即每次通话的线性时间)，记忆(即首次通话的线性时间，参数相同或较小的后续通话的零时间)，还是完全不共享(指数时间)。
简短的答案是，这是编译器。 :)