理解Haskell中的斐波那契数列

Question

fibs :: [Int]
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

这个代码生成了斐波那契数列。

我理解 :、zip 和 tail 的作用，但是我不理解 <- 在这里的作用。它在做什么？

- AR.

---

这不是一个守卫（guard），而是一个列表推导式（list comprehension）。http://www.haskell.org/haskellwiki/List_comprehension - pmr

你确定这是正确的斐波那契数列吗？在我看来，第一个元素应该是1。 - shuhalo

Answer 1

由于获得了赞，我将我的评论变成了一个回答。

你看到的不是一个守卫，而是列表推导。对于初学者来说，可以把它看作是一种表达数学集合符号的方式，如A={x|x元素N}，意思是：集合A是所有自然数的集合。在列表推导中，它将是[x | x <- [1..] ]。

您还可以对数字使用约束条件：[x | x <- [1..], x `mod` 2 == 0 ]等等。

有许多很好的Haskell教程涵盖了列表推导，甚至有一个关于Haskell资源的StackOverflow问题。

- pmr

Answer 2

唯一需要注意的是zip fibs (tail fibs)。 zip只是从其每个参数中制作成对列表。因此，如果您有两个像这样的列表：

[ 1, 2, 3, 4 ]
[ "a", "b", "c", "d" ]

将它们压缩会使它们：

[ (1,"a"), (2,"b"), (3,"c"), (4,"d") ]

左箭头（解构模式中的赋值）只是提取成对的元素，以便将它们相加。被压缩在一起的两个列表是 fibs 和 (tail fibs) -- 也就是斐波那契数列和偏移一个元素的斐波那契数列。Haskell 是惰性求值的，因此可以根据需要计算列表的任意数量元素。zip 也适用于此。

- amr

---

这两个斐波那契数列会一起计算一次还是分别独立计算两次？ - Thorbjørn Ravn Andersen

创建[(1,"a","A"),(2,"b","B"),...]的命令叫什么？它仍然是zip吗？解释得很好--它像Python中的zip一样工作，很酷。 - hhh

@hhh 嘿，朋友。看起来你需要 zip3，这很有趣。由于其类型系统的原因，在 Haskell 中实现通用的 zip 是可以理解为有点古怪的。在 Mathematica 中，你可以使用 Thread[{ls1, ls2, ls3}] 或者使用 Transpose 等方法。Python 也有一些“函数式编程”方面的东西。但就函数式编程而言，这些语言都无法与 APL 语言家族（如 J）相提并论，后者是函数式编程本身的一两个级别，并且属于它们自己更高的类别。 :) - amr

Answer 3

功能性编程的一个优点是，您可以像解决数学问题一样手动评估表达式：

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]
     = 0 : 1 : [ a + b | (a, b) <- zip [0, 1, ??] (tail [0, 1, ??])]

这里的 ?? 是尚未评估的部分，我们将在进行过程中填写它。

     = 0 : 1 : [ a + b | (a, b) <- zip [0, 1, ??] [1, ??])]
     = 0 : 1 : [ a + b | (a, b) <- (0, 1) : zip [1, ??] [??]]

请注意，我省略了对zip的评估，因为其定义未在此处给出，而详细信息与当前问题并不相关。这是我将用于显示每个数字对是如何由zip创建并由列表推导式使用的记号。

     = 0 : 1 : 0+1 : [ a + b | (a, b) <- zip [1, ??] [??]]
     = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, ??] [??]]

现在我们知道在??中的下一个元素是1：

     = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, 1, ??] [1, ??]]
     = 0 : 1 : 1 : [ a + b | (a, b) <- (1, 1) : zip [1, ??] [??]]
     = 0 : 1 : 1 : 1+1 : [ a + b | (a, b) <- zip [1, ??] [??]]
     = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, ??] [??]]

下一个元素是2：

     = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, 2, ??] [2, ??]]

清洗并重复。

- Code-Apprentice

Answer 4

就我个人而言，我认为以下版本更易于理解:

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

- fredoverflow

Answer 5

让我们来详细解释一下。 zip 将两个列表中的内容配对。因此，第一对 zip fibs (tail fibs) 给出了 (0, 1)，其总和为1。现在列表变成了 [0,1,1]。我们现在已经知道列表中的三个元素，因此列表推导式可以继续，从列表中获取下一个项和尾部中的下一个项，这给出了 (1,1) — 加在一起得到2。然后我们得到下一对，即 (1,2)，使序列中的下一个数字为3。这可以无限地继续下去，因为推导式将始终提供足够的项。

- Chuck

Answer 6

括号中的列表推导式：

[ a + b | (a, b) <- zip fibs (tail fibs)]

返回一个列表，其中包含输出（a + b），其中变量a和b来自结果

zip fibs (tail fibs)

- Viral Shah

Answer 7

我更喜欢更通用的

fib = 1 : [ x + y | (x, y) <- zip fib (0 : fib) ]

这最接近于以生成函数的形式理解斐波那契数列。如果对于n < 0，f(n) = 0，f(0) = 1，并且对于n > 0，f(n) = a*f(n-1) + b*f(n-2)，那么我们希望能够写出单行代码。

f(n) = 1_0 + a*f(n-1) + b*f(n-2)

并且让读者知道我们的意思。不幸的是，这需要一些未明确说明的约定才能有意义。

使用生成函数 g(t) = f(0) + f(1)t + f(2)t^2 + ... 我们可以写出等式

g(t) = 1 + a t g(t) + b t^2 g(t)

它可以轻松地以封闭形式解决 g(t)

g(t) = 1 / (1 - a t - b t^2)

这段 Haskell 代码

g = 1 : [ a*x + b*y | (x, y) <- zip g (0 : g) ]

实现相同的方程式。

- Syzygies

Answer 8

它定义了这个流程图，^(*)

             .---->>---->>----.
            /                  \ 
     <---- 0 <---- 1 ----<<--- (+) 
                    \          / 
                     *--->>---* 

它从自身中提取新的输入，但始终落后于生产点一个或两个位置，保持着两个“后指针”指向序列，相隔一个位置。

这体现在定义中，

--         .------->>------>>---.
--        /                      \
fibs  =  0 : 1 : [ a + b | a <- fibs 
{-            \  -}      | b <- tail fibs]
--             \                 /
--              *-->>------>>---*

使用并行列表推导式（:set -XParallelListComp 等）。

由于它只使用其最后两个元素，因此它等价于

    map fst . iterate (\(a, b) -> (b, a+b)) $ (0,1)

---

^(*) 这个图的执行过程如下：

                 .---->>---->>----.
                /                  \     0
       ? <---- 0 <---- 1 ----<<--- (+) 
                        \          /     1
                         *--->>---* 

                 .---->>---->>----.
                /                  \     1
     0,? <---- 1 <---- 1 ----<<--- (+) 
                        \          /     1
                         *--->>---* 

                 .---->>---->>----.
                /                  \     1
   0,1,? <---- 1 <---- 2 ----<<--- (+) 
                        \          /     2
                         *--->>---* 

                  .--->>---->>----.
                 /                 \     2
   0,1,1,? <--- 2 <--- 3 ----<<--- (+) 
                        \          /     3
                         *--->>---* 

                    .--->>--->>---.
                   /               \     3
   0,1,1,2,? <--- 3 <-- 5 ---<<--- (+) 
                        \          /     5
                         *--->>---* 
 ......

- Will Ness

Answer 9

这里的关键概念是惰性求值，这意味着如果值已经存在，那么就直接使用它而不需要进一步计算。比如说我已经得到了这个值并且任务完成了，我就不需要暂时计算未来的值。如果值不存在，那么就进行计算，当然这是惰性的，所以它不会去计算下一个需要的值。

我写了另一个实现来说明这一点，并使用“??”作为值占位符，如果需要的话就需要计算它。

fibs = 1:1:[ y!!1 + y!!0 | x<-[2..], y <- [[last (take x fibs), last (take (x-1) fibs)]] ]

我使用x来表示fibs中可用值的数量（不需要重新计算），并使用y作为[[last fib values]]嵌套列表。它的内部列表包含fibs中可用值的最后两个值。

因此，这是计算的过程：

1. x == 2，所以y是[last (take 2 fibs), last (take 1 fibs)]。惰性求值让我们只需取可用的值，不必担心未来的值。它告诉我要取fibs的前两个和第一个值，而这些值就在那里：1,1和1。现在y是[last [1,1], last [1]]，即[1,1]，要得到最终值，需要计算y!!1 + y!!0。这很明显，最终值是2。所以现在fibs是[1, 1, 2, ??]。

2. x == 3，与步骤1完全相同。y是[last [take 3 fibs], last [take 2 fibs]]，即[last [1,1,2], last [1,1]]，现在的值可用，所以我们可以直接取值并继续。最后，我们得到了第四个值3。

3. 就是这样，只需重复上述步骤，即可获得所有值，即使它是无限的。

这看起来不是很熟悉吗？就像使用递归函数计算斐波那契数列一样。现在我们让编译器自己来完成这些事情（参考）。我们在这里使用了惰性求值。

zip 的实现只是另一种表示[前几个斐波那契数列的值]的方法。你只需要稍作修改就能理解 zip 版本的斐波那契数列实现。

1. Haskell Wiki：惰性求值

2. 对于 <- 符号，请参阅：列表推导

- Eilliot