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

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

我不完全确定，但这是一个有根据的猜测：编译器假定fib n在不同的情况下可能有所不同n，因此每次都需要重新计算列表。毕竟，where声明中的位可能取决于n。也就是说，在这种情况下，整个数字列表基本上是一个函数n。没有 的版本n可以创建一次列表并将其包装在一个函数中。该列表不能取决于n传入的值，这很容易验证。该列表是一个常量，然后被索引到。当然，这是一个懒惰评估的常量，因此您的程序不会立即尝试获取整个（无限）列表。由于它是常量，因此可以在函数调用之间共享。它被记忆了，因为递归调用只需要查找列表中的值。由于fib版本一旦懒惰地创建列表，它只是计算得足以得到答案而不进行冗余计算。这里，“懒惰”意味着列表中的每个条目都是thunk（未评估的表达式）。当你做评估形实转换，就变成了价值，所以下一次访问它并没有重复计算。由于列表可以在调用之间共享，因此所有先前的条目都已在您需要下一个条目时计算。它本质上是一种基于GHC惰性语义的聪明且低廉的动态编程形式。我认为标准只规定它必须是非严格的，因此兼容的编译器可能会编译此代码而不进行 memoize。但是，在实践中，每个合理的编译器都会变得懒惰。有关第二种情况的工作原理的更多信息，请阅读理解递归定义的列表（根据zipWith的文件）。

Answer 2

首先，使用ghc-7.4.2，编译时-O2，非记忆版本并不是那么糟糕，Fibonacci数字的内部列表仍然为每个顶级调用函数记忆。但它不是，也不可能合理地，在不同的顶级电话中备忘。但是，对于其他版本，列表将在调用之间共享。这是由于单态限制。第一个是由一个简单的模式绑定（只有名称，没有参数）绑定，因此通过单态限制，它必须得到一个单态类型。推断类型是fib :: (Num n) => Int -> n并且这样的约束被默认（在没有默认声明的情况下另外说明）Integer，将类型修改为fib :: Int -> Integer因此，只有一个（类型[Integer]）列表要记忆。第二个是用函数参数定义的，因此它仍然是多态的，如果内部列表在调用中被记忆，则必须为每个类型记忆一个列表Num。那不切实际。在禁用单态限制或具有相同类型签名的情况下编译这两个版本，并且两者都表现出完全相同的行为。（对于较旧的编译器版本，情况并非如此，我不知道哪个版本首先使用它。）