通过斐波那契功能记忆什么机制?
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中的评估机制是by-need:当需要一个值时,将对其进行计算,并在准备再次输入时保持就绪状态。如果我们定义了一个列表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..]
技巧是使该列表被创建,并使该列表在调用 no shared 慷慨 edit: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
的每次新调用似乎都会重新创建其嵌套定义,因为它们中的任何一个[[could
n
的值([取决于)(感谢Vitus和Tikhon)指出这一点)。对于第一个定义,没有n
依赖,而对于第三个定义,则没有依赖,但是对fib3
的每个单独调用都会调用f
,这要小心,仅从内部相同级别范围的定义中调用fib3
的特定调用,因此相同的xs
被重用(即共享)用于fib3
的调用。但是没有什么可以阻止编译器认识到上述任何版本中的内部定义实际上是外部n
绑定的independent
fib3
显示局部共享,fib2
完全不共享。 最终取决于编译器和所使用的编译器优化,以及如何对其进行测试(将GHCI中的文件加载,是否编译,是否使用-O2或独立加载),以及它是否是单态或多态类型,行为可能会完全改变-是否表现出本地(每次通话)共享(即每次通话的线性时间),记忆(即第一次通话的线性时间,以及具有相同或更小的参数的后续通话的0时间),或在以下位置不共享全部(指数时间)。简短的答案是,这是编译器。 :)
n
。也就是说,在这种情况下,整个数字列表实际上是n
的函数。版本
无
n
可以一次创建列表并将其包装在函数中。列表cannot取决于传入的n
的值,这很容易验证。该列表是一个常量,然后将其索引到其中。当然,它是一个延迟计算的常量,因此您的程序不会尝试立即获取整个(无限)列表。由于它是一个常量,因此可以在函数调用之间共享。完全记住,因为递归调用只需要在列表中查找一个值。由于fib
版本会一次懒惰地创建列表,因此它只需进行足够的计算即可获得答案,而无需进行多余的计算。在这里,“懒惰”意味着列表中的每个条目都是一个笨拙的(未评估的表达式)。当您对[thunk]进行评估时,它成为一个值,因此下次访问它不会重复计算。由于该列表可以在呼叫之间共享,因此,在需要下一个条目时,所有先前的条目都已经计算出来。
not
记忆。但是,实际上,每个合理的编译器都会变得很懒惰。有关为何第二种情况完全起作用的更多信息,请阅读Understanding a recursively defined list (fibs in terms of zipWith)。[首先,使用ghc-7.4.2,并使用-O2
进行编译,未存储的版本还不错,对于该函数的每个顶级调用,斐波那契数字的内部列表仍然会被记住。但是,它不能也不能合理地在不同的顶级调用中被记忆。但是,对于其他版本,该列表在各个呼叫之间共享。
fib :: (Num n) => Int -> n
这样的约束默认(在没有默认声明的情况下)默认为Integer
,将类型固定为
fib :: Int -> Integer
因此,只有一个列表([Integer]
类型)要记住。
第二个函数定义了一个函数参数,因此它保持了多态性,如果内部列表是在调用之间存储的,则必须为Num
中的每种类型存储一个列表。那不切实际。
编译禁用单态性限制或具有相同类型签名的两个版本,并且两者表现出完全相同的行为。 (对于较早的编译器版本而言并非如此,我不知道首先使用哪个版本。)
您不需要Haskell的备忘功能。只有经验性编程语言才需要该功能。但是,Haskel是功能性语言,并且...
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