这个斐波那契函数如何记忆？

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)                    

Answer 1

Haskell中的评估机制是按需的:当需要一个值时,它会被计算并保持准备状态以防再次被要求.如果我们定义一些列表,xs=[0..]然后再询问它的第100个元素,xs!!99列表中的第100个插槽将"充实",99现在保留该数字,准备下次访问.

这就是"通过列表"这个技巧正在开发中.在正常的双向递归Fibonacci定义中,fib n = fib (n-1) + fib (n-2)函数本身从顶部被调用两次,导致指数爆炸.但是通过这个技巧,我们列出了中期结果的列表,然后"通过列表":

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

诀窍是导致该列表被创建,并导致该列表不会在调用之间消失(通过垃圾收集)fib.实现这一目标的最简单方法是命名该列表."如果你说出来,那就会留下来."

您的第一个版本定义了一个单形常量,第二个版本定义了一个多态函数.多态函数不能对可能需要服务的不同类型使用相同的内部列表,因此不共享,即没有memoization.

对于第一个版本,编译器对我们很慷慨,取出那个常量子表达式(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绑定,毕竟执行lambda提升,导致完全的memoization(多态定义除外).事实上,当使用单态类型声明并使用-O2标志编译时,这正是所有三个版本所发生的情况.使用多态类型声明,fib3展示本地共享并且fib2根本不共享.

最终,取决于编译器,使用的编译器优化,以及如何测试它(加载GHCI中的文件,编译与否,-O2与否,或独立),以及它是否具有单态或多态类型,行为可能完全改变 - 它是否表现出本地(每次通话)共享(即每次通话的线性时间),记忆(即第一次通话时的线性时间,以及使用相同或更小的参数的后续通话的0次),或根本没有共享(指数时间).

简而言之,这是一个编译器的事情.:)

Answer 2

我不完全确定,但这是一个有根据的猜测:

编译器假定fib n在不同的情况下可能不同n,因此每次都需要重新计算列表.毕竟,where声明中的位可能取决于n.也就是说,在这种情况下,整个数字列表基本上是一个函数n.

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

它被记忆了,因为递归调用只需要查找列表中的值.由于fib版本一旦懒惰地创建列表,它只是计算得足以得到答案而不进行冗余计算.这里,"懒惰"意味着列表中的每个条目都是thunk(未评估的表达式).当你做评估形实转换,就变成了价值,所以下一次访问它并没有重复计算.由于列表可以在调用之间共享,因此所有先前的条目都已在您需要下一个条目时计算.

它本质上是一种基于GHC惰性语义的聪明且低廉的动态编程形式.我认为标准只规定它必须是非严格的,因此兼容的编译器可能会编译此代码而不进行 memoize.但是,在实践中,每个合理的编译器都会变得懒惰.

有关第二种情况的工作原理的更多信息,请阅读理解递归定义的列表(根据zipWith的文件).

Answer 3

首先,使用ghc-7.4.2,编译时-O2,非记忆版本并不是那么糟糕,Fibonacci数字的内部列表仍然为每个顶级调用函数记忆.但它不是,也不可能合理地,在不同的顶级电话中备忘.但是,对于其他版本,列表将在调用之间共享.

这是由于单态限制.

第一个是由一个简单的模式绑定(只有名称,没有参数)绑定,因此通过单态限制,它必须得到一个单态类型.推断类型是

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

并且这样的约束被默认(在没有默认声明的情况下另外说明)Integer,将类型固定为

fib :: Int -> Integer

因此,只有一个(类型[Integer])列表要记忆.

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

在禁用单态限制或具有相同类型签名的情况下编译这两个版本,并且两者都表现出完全相同的行为.(对于较旧的编译器版本,情况并非如此,我不知道哪个版本首先使用它.)

Answer 4

您不需要 Haskell 的记忆功能。只有经验式编程语言需要该功能。然而，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