这个fibonacci函数是如何记忆的？
通过什么机制是这种斐波那契函数memoized？
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 ，准备下一次访问。
这就是“去一个清单”的诀窍，就是利用。 在正常双recursionFibonacci定义中， fib n = fib (n-1) + fib (n-2) ，函数本身从顶部调用两次，导致指数爆炸。 但是有了这个诀窍，我们为中期业绩列出了一份清单，然后“通过清单”：
fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]
诀窍是使该列表得到创build，并导致该列表不会在调用fib之间消失（通过垃圾回收）。 实现这个最简单的方法是命名该列表。 “如果你说出来，它会留下来。”
你的第一个版本定义了一个单形常量，第二个定义了一个多态函数。 一个多态函数不能使用相同的内部列表，它可能需要服务的不同types，所以不共享 ，即没有memoization。
在第一个版本中，编译器对我们很慷慨 ，把这个常量子expression式（ map fib' [0..] ）作为一个单独的可共享实体，但是没有这个义务。 实际上有些情况我们不希望它自动为我们做。
（ 编辑 ：）考虑这些重写：
fib1 = f fib2 n = fn fib3 n = fn where where where fi = xs !! ifi = xs !! ifi = 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心地不要调用外部范围的fib3 ，而是同一个级别的f 。
每次新的fib2调用似乎都会重新创build它的嵌套定义，因为它们中的任何一个（理论上）都可以根据 n的值进行不同的定义（感谢Vitus和Tikhon指出了这一点）。 第一个定义没有n依赖，第三个依赖，但是每个单独的调用fib3调用f ，这是谨慎的，只调用定义从相同级别的范围，内部这个特定的调用fib3 ，所以相同的xs被重用（即共享）的fib3调用。
但是没有任何东西阻止编译器认识到上述任何一个版本的内部定义事实上独立于外部n绑定，毕竟执行了lambda提升 ，导致完全存储（除了多态定义）。 实际上，当使用单形types声明并使用-O2标志编译时，所有这三个版本都会发生这种情况。 对于多态types声明， fib3展现了局部共享，而fib2根本不共享。
最终，根据编译器和编译器优化，以及如何testing（GHCI中加载文件，编译与否，使用-O2还是不使用，还是独立使用），以及它是单态还是多态都可能完全改变 – 是否展现本地（每次通话）共享（即每次通话的线性时间），记忆（即首次通话时的线性时间，以及相同或更小参数的后续通话时的0次），或者根本不共享指数时间）。
简单的答案是，这是一个编译器的东西。 🙂
我不完全确定，但这是一个有教养的猜测：
编译器假定fib n在不同的fib n可能不同，因此每次都需要重新计算列表。 毕竟， where语句中的位依赖于n 。 也就是说，在这种情况下，整个数字列表基本上是n的函数。
没有 n的版本可以创build一个列表，并将其包装在一个函数中。 列表不能取决于传入的n的值，这很容易validation。 该列表是一个常数，然后索引到。 当然，这是一个懒惰评估的常量，所以你的程序不会立即得到整个（无限）列表。 由于它是一个常量，它可以在函数调用中共享。
这是记忆，因为recursion调用只需要在列表中查找一个值。 由于fib版本懒惰地创build列表，它只是计算出足够的答案，没有多余的计算。 在这里，“懒”意味着列表中的每个条目都是一个thunk（一个未评估的expression式）。 当你评估thunk时，它变成一个值，所以下次访问它不会重复计算。 由于列表可以在通话之间共享，所有以前的条目已经在您需要下一个条目的时候计算出来了。
它基本上是基于GHC懒惰语义的dynamic规划的一种聪明而廉价的forms。 我认为这个标准只是规定它是非严格的 ，所以一个兼容的编译器可能会编译这个代码而不记忆。 但是，实际上，每个合理的编译器都是懒惰的。
有关第二种情况为什么可以运行的更多信息，请阅读理解recursion定义的列表（按照zipWith的语法） 。
首先，对于使用-O2编译的ghc-7.4.2，未记忆的版本并没有那么糟糕，斐波纳契数字的内部列表对于每个对该函数的顶级调用仍然记忆。 但是不能也不能合理地在不同的顶级通话中进行记忆。 但是，对于其他版本，该列表是通过呼叫共享的。
这是由于单态的限制。
首先是绑定一个简单的模式绑定（只有名称，没有参数），因此通过单态限制它必须得到一个单形types。 推断的types是
fib :: (Num n) => Int -> n
并且这样一个约束被默认（在没有默认声明的情况下）默认为Integer ，修改types为
fib :: Int -> Integer
因此，只有一个列表（types[Integer] ）来记忆。
第二个是用一个函数参数定义的，因此它仍然是多态的，如果内部列表是通过调用记忆的，那么在Num每个types都必须logging一个列表。 这是不实际的。
编译禁用单态限制或具有相同types签名的两个版本，并且都显示完全相同的行为。 （对于较老的编译器版本，这是不正确的，我不知道哪个版本是首先做的。）
你不需要Haskell的memoize函数。 只有有效的编程语言才需要这些function。 然而，Haskel是function性的语言和…
所以，这是非常快的斐波那契algorithm的例子：
fib = zipWith (+) (0:(1:fib)) (1:fib)
zipWith从标准的function前奏：
zipWith :: (a->b->c) -> [a]->[b]->[c] zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2) zipWith _ _ _ = []
testing：
print $ take 100 fib
输出：
[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]
所用时间：0.00018s
