斐波那契数列生成
Fibonacci sequence generation
我正在写一个斐波那契数列生成器，我试图理解 Haskell
中的以下代码
fibs = 1 : 1 : zipWith (+) 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]。但是，要完全评估 fibs，它会继续评估 x，我们回到前面的步骤。
这是正确的吗？
此外，我注意到当我运行上面的程序ghci时，它会立即提示它当前计算的斐波那契数列，为什么？它不是应该在完成所有计算后打印结果吗？
所以，你的大部分推理都是正确的。特别是，您正确地描述了列表中的每个新元素是如何根据旧元素进行评估的。你也是正确的 fully 评估 fibs 需要重复你概述的步骤，事实上，会永远循环。
您缺少的关键要素是我们不必完全评估列表。像 fibs = ... 这样的绑定只是为表达式分配一个名称；它不需要评估整个列表。 Haskell 只会评估列表中需要的部分 运行 main。因此，例如，如果我们的 main 是
main = print $ fibs !! 100
Haskell 只会计算 fibs 的前 100 个元素（按照您列出的步骤），但不需要更多，也不会永远循环。
此外，即使我们正在评估整个事情（将永远循环），我们也可以在进行时使用我们计算的部分。这正是当您在 ghci 中看到 fibs 的值时发生的事情：它会在计算每个元素时尽可能多地打印，而不必等到整个列表准备就绪。
看到 GHCi 的严格性
您可以使用 :sprint 命令查看在 ghci 中评估了多少列表，该命令将打印一个 Haskell 数据结构，其中 _ 用于尚未评估（称为 "thunks"）。您可以使用它来查看 fibs 如何在行动中得到评估：
Prelude> let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = _
糟糕，这不是我们所期望的！实际上，这是单态限制缺乏的一个问题！ fibs 获取多态类型
Prelude> :t fibs
fibs :: Num a => [a]
这意味着每次使用它时它的行为就像一个函数调用，而不像一个普通值。 （在后台，GHC 将 Num 类型 class 实例化为将字典传递给 fibs；它的实现类似于 NumDictionary a -> [a] 函数。）
要真正理解发生了什么，我们需要明确地fibs 单态。我们可以通过从限制处于活动状态的模块加载它或为其提供显式类型签名来实现。让我们做后者：
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 : _
现在您看到了：您可以看到列表的哪些部分需要评估，哪些部分不需要评估第 10 个元素。您可以尝试使用其他列表或其他惰性数据结构，以更好地了解后台发生的事情。
另外，你可以看看 my blog post 关于这种懒惰的内容。它更详细地介绍了 fibs 示例（带有图表！），并讨论了如何使用这种方法进行一般记忆和动态编程。
我正在写一个斐波那契数列生成器，我试图理解 Haskell
中的以下代码fibs = 1 : 1 : zipWith (+) 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]。但是，要完全评估 fibs，它会继续评估 x，我们回到前面的步骤。
这是正确的吗？
此外，我注意到当我运行上面的程序ghci时，它会立即提示它当前计算的斐波那契数列，为什么？它不是应该在完成所有计算后打印结果吗？
所以，你的大部分推理都是正确的。特别是，您正确地描述了列表中的每个新元素是如何根据旧元素进行评估的。你也是正确的 fully 评估 fibs 需要重复你概述的步骤，事实上，会永远循环。
您缺少的关键要素是我们不必完全评估列表。像 fibs = ... 这样的绑定只是为表达式分配一个名称；它不需要评估整个列表。 Haskell 只会评估列表中需要的部分 运行 main。因此，例如，如果我们的 main 是
main = print $ fibs !! 100
Haskell 只会计算 fibs 的前 100 个元素（按照您列出的步骤），但不需要更多，也不会永远循环。
此外，即使我们正在评估整个事情（将永远循环），我们也可以在进行时使用我们计算的部分。这正是当您在 ghci 中看到 fibs 的值时发生的事情：它会在计算每个元素时尽可能多地打印，而不必等到整个列表准备就绪。
看到 GHCi 的严格性
您可以使用 :sprint 命令查看在 ghci 中评估了多少列表，该命令将打印一个 Haskell 数据结构，其中 _ 用于尚未评估（称为 "thunks"）。您可以使用它来查看 fibs 如何在行动中得到评估：
Prelude> let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = _
糟糕，这不是我们所期望的！实际上，这是单态限制缺乏的一个问题！ fibs 获取多态类型
Prelude> :t fibs
fibs :: Num a => [a]
这意味着每次使用它时它的行为就像一个函数调用，而不像一个普通值。 （在后台，GHC 将 Num 类型 class 实例化为将字典传递给 fibs；它的实现类似于 NumDictionary a -> [a] 函数。）
要真正理解发生了什么，我们需要明确地fibs 单态。我们可以通过从限制处于活动状态的模块加载它或为其提供显式类型签名来实现。让我们做后者：
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 : _
现在您看到了：您可以看到列表的哪些部分需要评估，哪些部分不需要评估第 10 个元素。您可以尝试使用其他列表或其他惰性数据结构，以更好地了解后台发生的事情。
另外，你可以看看 my blog post 关于这种懒惰的内容。它更详细地介绍了 fibs 示例（带有图表！），并讨论了如何使用这种方法进行一般记忆和动态编程。