这个斐波那契函数是如何被记忆化的？

Question

这个斐波那契函数是通过什么机制进行记忆化的？

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)                    

- bjornars

---

有点不相关，fib 0没有终止：你可能希望 fib' 的基本情况是 fib' 0 = 0 和 fib' 1 = 1。 - huon

请注意，第一版可以更简洁：fibs = 1:1:zipWith (+) fibs (tail fibs) 和 fib = (fibs !!)。 - Bastian

Answer 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，而是同级的f。

每次调用fib2似乎都会重新创建其嵌套定义，因为它们中的任何一个可能（理论上）根据n的值而被定义得不同（感谢Vitus和Tikhon的指出）。在第一个定义中，没有n依赖性，在第三个定义中有一个依赖性，但是对于fib3的每个独立调用，都会调用到仅从同级作用域内部调用的f，因此相同的xs被重复使用（即共享）用于该调用的fib3。

但是，没有什么能阻止编译器认识到上述任意版本中的内部定义实际上与外部n绑定无关，以执行lambda lifting，结果完全记忆化（除了多态定义）。事实上，当声明具有单态类型并使用-O2标志编译时，所有三个版本都会发生这种情况。对于多态类型声明，fib3表现出本地共享，fib2则根本不共享。

最终，取决于编译器、使用的编译器优化、以及您如何测试它（在GHCI中加载文件、已编译或未编译、使用-O2还是不使用-O2、独立运行），以及它是否获得单态或多态类型，行为可能完全改变-无论是显示本地（每次调用）共享（即每次调用的线性时间）、记忆化（即第一次调用的线性时间，以及具有相同或较小参数的后续调用的0时间）还是根本不共享（指数时间）。

简短的答案是，这是编译器的事情。:)

- Will Ness

---

仅需要纠正一个小细节：第二个版本没有得到分享主要是因为本地函数 fib' 被重新定义了，对于每个 n 都不一样，所以 fib 1 中的 fib' ≠ fib 2 中的 fib'，这也意味着列表是不同的。即使你把类型固定为单形式（monomorphic），它仍然表现出这种行为。 - Vitus

where子句引入了共享的概念，就像let表达式一样，但它们往往会隐藏这样的问题。稍微更明确地重写一下，你会得到这个：http://hpaste.org/71406 - Vitus

关于您的重写还有一个有趣的点：如果您给它们单态类型（即Int -> Integer），那么fib2将以指数时间运行，fib1和fib3都以线性时间运行，但fib1也被记忆化 - 再次因为对于fib3，局部定义在每个n上都被重新定义了。 - Vitus

@misterbee 但确实希望编译器能够提供某种保证；对特定实体的内存驻留有某种控制。有时我们想要共享，有时我们想要防止共享。我想/希望这应该是可能的... - Will Ness

@ElizaBrandt 我的意思是有时候我们想要重新计算一些繁重的东西，这样它就不会一直保留在内存中——也就是说，重新计算的成本比巨大的内存保留成本更低。一个例子是幂集的创建：在 pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]] 中，我们确实希望 pwr xs 被独立地计算两次，这样它就可以在生成和消耗时被动态回收。 - Will Ness

Answer 2

我不是完全确定，但这是我的一个合理猜测：

编译器假设fib n在不同的n上可能不同，因此每次都需要重新计算列表。毕竟，在where语句内部的位数可能取决于n。也就是说，在这种情况下，整个数字列表本质上是n的函数。

没有n版本可以创建一次列表并将其包装在函数中。列表不能依赖于传入的n的值，这很容易验证。列表是一个常量，然后被索引。当然，它是一个惰性求值的常量，因此你的程序不会立即尝试获取整个（无限）列表。由于它是一个常量，它可以在函数调用之间共享。

它是memoize的，因为递归调用只需在列表中查找一个值。由于fib版本只创建了一次惰性列表，它只计算足够的内容以获得答案而不进行冗余计算。这里，“惰性”意味着列表中的每个条目都是thunk（未评估表达式）。当你评估thunk时，它变成一个值，因此下次访问它时不会重复计算。由于列表可以在调用之间共享，所以在需要下一个条目之前，所有先前的条目都已经计算完毕。

这本质上是基于GHC的惰性语义的巧妙而低廉的动态编程形式。我认为标准只指定它必须非严格，因此符合要求的编译器可能会编译此代码以不进行memoize。但是，在实践中，每个合理的编译器都将是惰性的。

有关为什么第二种情况可行的更多信息，请阅读Understanding a recursively defined list (fibs in terms of zipWith)。

- Tikhon Jelvis

---

你是指“fib' n' 在不同的 n 上可能会有所不同”吗？ - Will Ness

我觉得我表达不够清晰：我的意思是，fib 中的所有内容，包括 fib'，在每个不同的 n 上都可能不同。我认为原始示例有点令人困惑，因为 fib' 也取决于它自己的 n，这会掩盖其他 n 的影响。 - Tikhon Jelvis

Answer 3

首先，对于使用 -O2 编译的 ghc-7.4.2 版本，非记忆化版本并不差，对于每个顶层调用该函数的内部斐波那契数列仍然被记忆化。但是，它不能在不同的顶层调用之间进行记忆化，因此无法进行优化。然而，对于另一个版本，该列表在调用之间是共享的。

这是由于单态限制引起的。

第一个版本仅通过简单的模式绑定（仅名称，没有参数）进行绑定，因此根据单态限制它必须获得单态类型。 推断出的类型是：

fib :: (Num n) => Int -> n

如果没有默认声明表明其它类型，这样的限制条件会被默认为 Integer 类型，从而固定了该类型。

fib :: Int -> Integer

因此只有一个类型为[Integer]的列表可供存储。

第二个列表是通过一个函数参数定义的，因此它保持多态性，如果在调用过程中对内部列表进行了记忆化，那么每种Num类型都必须记忆化一个列表，这是不可行的。

禁用单态化限制或使用相同的类型签名编译两个版本，它们都会表现出完全相同的行为。（这在早期的编译器版本中不是真的，我不知道哪个版本首先这样做。）

- Daniel Fischer

---

为什么为每种类型记忆化列表是不切实际的？原则上，GHC是否可以创建一个字典（类似于调用类型类约束函数的字典），以包含在运行时遇到的每个Num类型的部分计算列表？ - misterbee

@misterbee 原则上，这是可能的，但如果程序在许多类型上调用 fib 1000000，那么会消耗大量内存。为了避免这种情况，需要一种启发式方法，在缓存增长过大时将其清除。而且这样的记忆化策略也适用于其他函数或值，因此编译器必须处理可能需要记忆化的许多类型的问题。我认为可以使用合理的启发式实现（部分）多态记忆化，但我怀疑这是否值得。 - Daniel Fischer

Answer 4

你不需要在Haskell中使用memoize函数。只有在面向过程的编程语言中才需要这些函数。然而，Haskell是一种函数式语言，所以...

因此，以下是非常快速的斐波那契算法示例：

fib = zipWith (+) (0:(1:fib)) (1:fib)

zipWith是来自标准Prelude的函数:

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

测试:

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.00018秒

- Валерий Кобзарь