使用Haskell中的列表推导表示Fibonacci数

Question

我编写了以下代码来生成包含Fibonacci数字的列表.

fibonacci = [a + b | a <- 1:fibonacci, b <- 0:1:fibonacci]

我希望列表[1,2,3,5,8,13..]的输出是,但输出不是Fibonacci序列.

我不太明白为什么它不起作用.

我的理由是,如果斐波那契数字是[1,2,3,5,8,13..]那么这将是等于2名列表之[1,1,2,3,5,8,13..]和[0,1,1,2,3,5,8,13..],这相当于1:[1,2,3,5,8,13..]和0:1:[1,2,3,5,8,13..]或1:fibonacci和0:1:fibonacci

我已经查找了实现此序列的其他方法,但我真的想知道为什么我的代码不起作用.

Answer 1

问题

附:

fibonacci = [a + b | a <- 1:fibonacci, b <- 0:1:fibonacci]

您正在生成两个列表的所有可能组合.例如:

x = [a + b | a <- [1, 2], b <- [3, 4]]

结果将是:

[1 + 3, 1 + 4, 2 + 3, 2 + 4]

Live demo

同 zipWith

你最接近的是zipWith:

fibonacci :: [Int]
fibonacci = zipWith (+) (1:fibonacci) (0:1:fibonacci)

Live demo

Answer 2

列表理解模型

• 非确定性
• 笛卡尔积
• 嵌套for-loops

这些都是等价的.所以你的Fibonacci序列是错误的,因为它的计算方式太多了.在伪代码中它有点像

fibonacci = 
  for i in 1:fibonacci:
    for j in 0:1:fibonacci:
      i + j

你真正想要的是将列表压缩在一起,按照斐波纳契的长度而不是它的平方来执行计算.要做到这一点,我们可以使用zipWith,并用一点代数,得到标准的"棘手的纤维"

fibonacci = zipWith (+) (1:fibonacci) (0:1:fibonacci)
fibonacci = zipWith (+) (0:1:fibonacci) (1:fibonacci)          -- (+) is commutative
fibonacci = zipWith (+) (0:1:fibonacci) (tail (0:1:fibonacci)) -- def of tail

然后我们定义

fibonacci' = 0:1:fibonacci
fibonacci' = 0:1:zipWith (+) (0:1:fibonacci) (tail (0:1:fibonacci))
fibonacci' = 0:1:zipWith (+) fibonacci' (tail fibonacci')

这是标准的

fibonacci = drop 2 fibonacci'

您还可以使用ParallelListComprehension扩展名,它允许您使用稍微不同的语法在列表推导中进行压缩

{-# ParallelListComp #-}
fibonacci = [a + b | a <- 1:fibonacci | b <- 0:1:fibonacci]

> take 10 fibonacci
[1,2,3,5,8,13,21,34,55,89]

Answer 3

列表推导不是那样的.你已经写了一个嵌套的遍历,而你想要做的是一个zip.

要了解其中的差异,请考虑:

Prelude> let fibs = [ a + b | (a,b) <- zip (1 : fibs) (0 : 1 : fibs) ]
Prelude> take 10 fibs
[1,2,3,5,8,13,21,34,55,89]

哪个有效,正如您所期望的那样.

Haskell有一个语法扩展,允许并行理解,所以语法为你做了一个zip.你可以启用它-XParallelListComp然后写:

Prelude> let fibs = [ a + b | a <- 1 : fibs | b <- 0 : 1 : fibs ]
Prelude> take 10 fibs
[1,2,3,5,8,13,21,34,55,89]