了解Haskell的斐波那契

Question

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

这会生成斐波纳契数列.

我理解的卫兵,行为:,zip和tail,但我不明白<-.这是做什么的？

Answer 1

由于赞成,我将我的评论写成答案.

你看到的不是守卫,而是列表理解.对于初学者来说,将其视为表达数学集符号的方式,如A = {x | x元素N}这意味着以下几点:集合A是所有自然数的集合.在列表理解中[x | x <- [1..] ].

您还可以对数字使用约束:[x | x <- [1..], x `mod` 2 == 0 ]以及许多其他内容.

那里有很多好的haskell turorials,它们涵盖了列表理解,甚至还有关于haskell资源的StackOverflow问题.

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)-换句话说,斐波纳契数列,与斐波那契序列通过1个元素的偏移量.Haskell是懒惰评估的,所以它可以计算列表,但需要很多元素.这也适用于拉链.

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, ??] [??]]

现在我们知道 中的下一个元素??是 a 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, ??]]

冲洗并重复。

Answer 4

我们来扩展一下。

\n\n

zip根据两个列表的内容创建对。所以第一对zip fibs (tail fibs)给我们的是(0, 1)，加起来是 1。所以现在的列表是[0,1,1]。现在我们知道列表中的三个元素，因此列表理解可以继续，从列表中获取下一个项目，并从尾部获取下一个项目，这将(1,1)\xe2\x80\x94 加在一起，得到 2。然后我们得到下一个对，即(1,2)，使序列中的下一个数字为 3。这可以无限地继续，因为推导式总是会提供足够的项目。

\n

Answer 5

就其价值而言，我发现以下版本更容易理解：

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

Answer 6

括号中的列表理解：

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

返回一个包含输出 (a + b) 的列表，其中变量 a 和 b 来自以下结果

zip fibs (tail fibs)