斐波纳契序列的生成 [英] Fibonacci sequence generation

问题描述

$ b fibs = 1：1：zipWith

我写了一个斐波那契序列生成器，并试图理解Haskell中的以下代码。 （+）fibs（tail fibs）


我知道 zipWith 是，但我不完全知道该程序是如何执行的，以及它为什么生成所有的斐波那契数字。我试图理解为什么它不会终止在函数式语言中使用环境概念，如下所示：

最初，由于Haskell的懒惰评估，绑定在 env 应该是 fibs：[1,1，x] ，然后评估 fibs x ，它是 zipWith（+）fibs（tail fibs）。在评估 zipWith 时，它得到 fibs：[1,1,2，x] ，这也是因为懒惰的评估Haskell。并且 env 中的 fibs 绑定到 [1,1,2，x] code>在这个时候。但是，要充分评估 fibs ，它会继续评估 x ，然后回到前面的步骤。

这是正确的吗？

另外，我注意到当我在 ghci ，它会立即提示它当前计算的斐波那契数列，为什么？不应该在结果完成所有计算后打印结果吗？ 所以，大部分推理都是正确的。特别是，您正确地描述了列表中每个新元素是如何评估旧元素的。您完全评估 fibs 需要重复您列出的步骤并且实际上会永远循环。

$也是正确的。 b
$ b

缺少的关键因素是我们无需完全评估列表。像 fibs = ... 这样的绑定只是为表达式分配一个名称;它不需要评估整个列表。 Haskell只会评估运行 main 的列表。所以，例如，如果我们的 main 是

  main = print $ fibs！ 100 
  

Haskell将只计算 fibs （按照你列出的步骤），但不需要任何更多的，不会永远循环。





此外，即使我们 fibs 的值时，就会发生这种情况：在每个元素被计算时它会尽可能多地进行打印，并且不必等到整个列表已准备就绪。

在GHCi中查看严格性

您可以看到有多少列表在 ghci 使用：sprint 命令，它将用 _ 。你可以用这个来看看 fibs 是如何评估的：

 前奏>让fibs = 1：1：zipWith（+）fibs（tail fibs）
 Prelude> ：sprint fibs 
 fibs = _ 
 Prelude>打印$ fibs！ 10 
 89 
 Prelude> ：sprint fibs 
 fibs = _ 
  

糟糕，这不是我们所期望的！事实上，这是一种情况，即单态限制的缺少是一个问题！ fibs 得到一个多态类型



  Prelude> ：t fibs 
 fibs :: Num a => [a] 
  

这意味着它在每次使用时都像函数调用一样，而不像普通函数值。 （在后台，GHC实现了将 Num 类型类传递给 fibs 的字典;它的实现类似于 NumDictionary a - > [a] 函数。）

为了真正理解发生了什么，我们需要明确地制作 fibs monomorphic 。我们可以通过从限制处于活动状态的模块加载它或通过给它一个明确的类型签名来完成此操作。让我们来做后者：

  Prelude>让fibs :: [Integer]; fibs = 1：1：zipWith（+）fibs（tail fibs）
 Prelude> ：sprint fibs 
 fibs = _ 
 Prelude>打印$ fibs！ 10 
 89 
 Prelude> ：sprint fibs 
 fibs = 1：1：2：3：5：8：13：21：34：55：89：_ 
  

现在你可以看到列表中哪些部分需要评估，哪些部分不能获得第10个元素。您可以使用其他列表或其他懒惰的数据结构，以便了解后台正在进行的操作。

另外，您可以查看我的博客文章关于这种懒惰。它详细介绍了 fibs 示例（使用图表！）并讨论如何将这种方法用于常规记忆和动态编程。

I was writing a fibonacci sequence generator, and I was trying to understand the following code in Haskell

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

I understand what zipWith is, but I do not exactly know how the program executes and why it does generate all the fibonacci numbers. I was trying to understand why it does not terminate using the environment concept in functional languages as follows:

Initially, because Haskell's lazy evaluation, the binding in the env should be fibs : [1,1,x], then to evaluate fibs, the interpreter evaluates x which is zipWith (+) fibs (tail fibs) in this case. When evaluating zipWith, it gets fibs : [1,1,2,x], again because of the lazy evaluation of Haskell. And fibs in env is bound to [1,1,2,x] at this time. However, to fully evaluate fibs, it continues to evaluate x and we go back to the previous steps.

Is this correct?

Besides, I noticed that when I ran the program above in ghci, it instantly prompts the fibonacci sequence it currently has computed, why? Shouldn't it print the result once it finishes all the computation?

解决方案

So, most of your reasoning is correct. In particular, you described correctly how each new element of the list is evaluated in terms of older ones. You are also correct that to fully evaluate fibs would require repeating the steps you outlined and would, in fact, loop forever.

The key ingredient you're missing is that we don't have to fully evaluate the list. A binding like fibs = ... just assigns a name to the expression; it does not require evaluating the whole list. Haskell will only evaluate as much of the list as it needs to run main. So, for example, if our main is

main = print $ fibs !! 100

Haskell will only calculate the first 100 elements of fibs (following the steps you outlined) but will not need any more than that and will not loop forever.

Moreover, even if we are evaluating the whole thing (which will loop forever), we can use the parts we've calculated as we go along. This is exactly what's happening when you see the value of fibs in ghci: it prints as much as it can as each element is being calculated and does not have to wait until the whole list is ready.

Seeing Strictness in GHCi

You can see how much of a list is evaluated in ghci using the :sprint command which will print a Haskell data structure with _ for the parts that haven't been evaluated yet (called "thunks"). You can use this to see how fibs gets evaluated in action:

Prelude> let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = _

Oops, that's not what we expected! In fact, this is a case where the lack of the monomorphism restriction is a problem! fibs gets a polymorphic type

Prelude> :t fibs
fibs :: Num a => [a]

which means it behaves like a function call each time you use it, not like a normal value. (In the background, GHC implements instantiating the Num type class as passing in a dictionary to fibs; it's implemented like a NumDictionary a -> [a] function.)

To really understand what's going on, we'll need to make fibs monomorphic explicitly. We can do this by loading it from a module where the restriction is active or by giving it an explicit type signature. Let's do the latter:

Prelude> let fibs :: [Integer]; fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = 1 : 1 : 2 : 3 : 5 : 8 : 13 : 21 : 34 : 55 : 89 : _

And there you are: you can see which parts of the list needed to be evaluated and which ones didn't to get the 10th element. You can play around with other lists or other lazy data structures to get a good feel for what's going on in the background.

Also, you can take a look at my blog post about this sort of laziness. It goes into greater detail about the fibs example (with diagrams!) and talks about how to use this approach for general memoization and dynamic programming.

这篇关于斐波纳契序列的生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！