haskell - 这个斐波那契函数是如何内存的？

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现在，准备下次访问。

这就是“遍历列表”这个技巧所利用的。在正常的双重递归斐波那契定义中，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它小心地只从同级范围调用定义，在 fib3 的特定调用内部。 ，所以同样xs对于 fib3 的调用被重用(即共享) .

但没有什么可以阻止编译器认识到上述任何版本中的内部定义实际上独立外部 n绑定(bind)，执行lambda lifting毕竟，导致完全内存(多态定义除外)。事实上，当使用单态类型声明并使用 -O2 标志编译时，这正是所有三个版本所发生的情况。使用多态类型声明，fib3展品本地分享及fib2根本没有分享。

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

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