120

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

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)
4

4 回答 4

96

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)

所以真正的故事似乎是关于嵌套范围定义的。第 1 个定义没有外部作用域，第 3 个定义注意不要调用 outer-scope fib3，而是调用 same-level f。

每个新的调用fib2似乎都重新创建了它的嵌套定义，因为它们中的任何一个（理论上）都可以根据 的值进行不同的定义（感谢Vitusn和 Tikhon 指出这一点）。第一个定义没有n依赖，第三个有依赖，但是每个单独的调用fib3调用f都小心地只调用来自同级范围的定义，这个特定调用的内部fib3，所以同样xs得到重用（即共享）来调用fib3.

但是没有什么能阻止编译器认识到上述任何版本中的内部定义实际上是独立于外部绑定的，毕竟n执行lambda 提升，导致完全记忆（多态定义除外）。事实上，当使用单态类型声明并使用 -O2 标志编译时，这正是所有三个版本所发生的情况。使用多态类型声明，fib3展示本地共享和fib2根本不共享。

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

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

于 2012-07-13T08:39:01.747 回答
23

我不完全确定，但这里有一个有根据的猜测：

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

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

它完全被记住了，因为递归调用只需要在列表中查找一个值。由于该fib版本会懒惰地创建一次列表，因此它只计算足以得到答案而无需进行冗余计算。这里，“懒惰”意味着列表中的每个条目都是一个 thunk（一个未计算的表达式）。当您确实评估 thunk 时，它会变成一个值，因此下次访问它不会重复计算。由于列表可以在调用之间共享，所有之前的条目都已经在您需要下一个条目的时间计算出来。

它本质上是一种基于 GHC 的惰性语义的智能且廉价的动态编程形式。我认为该标准仅指定它必须是non-strict，因此兼容的编译器可能会编译此代码以不记忆。然而，在实践中，每个合理的编译器都会变得懒惰。

有关第二种情况为何有效的更多信息，请阅读理解递归定义的列表（用 zipWith 表示的 fibs）。

于 2012-07-13T08:01:33.440 回答
20

首先，使用 ghc-7.4.2，编译-O2，非记忆版本还不错，斐波那契数字的内部列表仍然为函数的每个顶级调用而记忆。但它不是，也不能合理地在不同的顶级调用中被记忆。但是，对于其他版本，该列表在调用之间共享。

这是由于单态性限制。

第一个由简单的模式绑定（只有名称，没有参数）绑定，因此受单态限制，它必须获得单态类型。推断的类型是

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

并且这样的约束被默认为（在没有默认声明的情况下）Integer，将类型固定为

fib :: Int -> Integer

因此只有一个列表（类型[Integer]）要记忆。

第二个是用函数参数定义的，因此它仍然是多态的，如果内部列表在调用中被记忆，则必须为Num. 那是不切实际的。

在禁用单态限制或使用相同类型签名的情况下编译两个版本，并且都表现出完全相同的行为。（对于较旧的编译器版本并非如此，我不知道哪个版本首先做到了。）

于 2012-07-13T08:47:36.923 回答
5

Haskell 不需要 memoize 功能。只有经验性编程语言需要这些功能。但是，Haskel 是函数式语言，并且...

所以，这是一个非常快速的斐波那契算法的例子：

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

于 2015-04-23T15:19:58.873 回答