这个斐波那契如何？
这种斐波纳契函数是通过什么机制记忆的？
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 ，准备下一次访问。
这就是“开列表”的诀窍，就是利用。 在正常的双递归斐波那契定义中， fib n = fib (n-1) + fib (n-2) ，函数本身从顶部调用两次，导致指数爆炸。 但有了这个诀窍，我们为中期结果列出了一份清单，然后“通过清单”：
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心地不要调用外部范围的fib3 ，而是调用同一个级别的f 。
每次新的fib2调用似乎都会重新创建它的嵌套定义，因为它们中的任何一个（理论上）都可以根据n的值进行不同的定义（感谢Vitus和Tikhon指出了这一点）。 第一个定义没有n依赖，第三个有依赖关系，但是每个单独的调用fib3调用f ，这个调用只能从同级作用域调用定义，在这个特定的fib3调用内部，所以相同的xs被重用（即共享）用于调用fib3 。
但是没有任何东西阻止编译器认识到上述任何版本中的内部定义实际上独立于外部n绑定，毕竟执行了lambda提升，从而导致完全记忆（除了多态定义）。 实际上，当使用单形类型声明并使用-O2标志进行编译时，所有三个版本都会发生这种情况。 使用多态类型声明时， fib3展现出局部共享，而fib2根本不共享。
最终，根据编译器，编译器优化以及测试方式（GHCI中加载文件，编译与否，使用-O2还是不使用，还是单独使用），以及它是单态还是多态都可能完全改变 - 是否展示本地（每次通话）共享（即每次通话的线性时间），记忆（即第一次通话时的线性时间，以及相同或更小参数的后续通话时的0次），或根本不共享指数时间）。
简而言之，这是一个编译器。 :)
我并不完全确定，但这是一个有教养的猜测：
编译器假定fib n可能是在不同的不同的n ，因此需要在每次重新计算清单。 毕竟， where语句中的位可能依赖于n 。 也就是说，在这种情况下，整个数字列表基本上是n的函数。
没有n的版本可以创建一次列表并将其包装在一个函数中。 该列表不能取决于传入的n的值，这很容易验证。 该列表是一个常数，然后索引到。 当然，这是一个懒惰评估的常量，因此您的程序不会立即尝试获取整个（无限）列表。 由于它是一个常量，它可以在函数调用中共享。
它被记忆了，因为递归调用只需要在列表中查找一个值。 由于fib版本懒惰地创建列表，它只是计算出足够的答案而不需要进行冗余计算。 这里，“懒”意味着列表中的每个条目都是一个thunk（一个未评估的表达式）。 当你评估thunk时，它会变成一个值，所以下次访问它不会重复计算。 由于列表可以在通话之间共享，所有以前的条目已经在您需要下一条时计算出来。
它基本上是基于GHC懒惰语义的动态规划的一种聪明而廉价的形式。 我认为这个标准只规定它必须是非严格的，所以一个兼容的编译器可能会编译这个代码来不记忆。 但是，实际上，每个合理的编译器都会变得懒惰。
有关第二种情况为什么可以运行的更多信息，请阅读理解递归定义列表（按照zipWith的含义）。
首先，对于使用-O2编译的ghc-7.4.2，未记忆的版本并没有那么糟糕，对于函数的每个顶级调用，斐波纳契数字的内部列表仍然记忆。 但它不是，也不可能合理地在不同的顶级通话中被记忆。 但是，对于其他版本，该列表是通过呼叫共享的。
这是由于单态限制。
第一种是由一个简单的模式绑定（只有名称，没有参数）绑定，因此通过单态限制它必须得到一个单形类型。 推断的类型是
fib :: (Num n) => Int -> n
并且这样一个约束得到默认（在没有默认声明的情况下）默认为Integer ，将类型固定为
fib :: Int -> Integer
因此，只有一个列表（类型[Integer] ）来记忆。
第二个是用一个函数参数定义的，因此它仍然是多态的，并且如果内部列表是通过呼叫记忆的，那么一个列表将不得不为每个Num类型记忆。 这是不实际的。
编译禁用单态限制或具有相同类型签名的两个版本，并且都显示完全相同的行为。 （对于较老的编译器版本，这是不正确的，我不知道哪个版本首先做到了。）
链接地址: http://www.djcxy.com/p/43183.html下一篇: Rewriting as a practical optimization technique in GHC: Is it really needed?