是否有可能使用[编辑:一个非常有限的知识集]来创建斐波那契数列?

Question

例如:

let f = [ a | a <- [1..], a == a - 1]

我只是好奇。这似乎是可能的，但我不太明白它是如何工作的。这个问题更多的是为了理解Haskell是如何工作的，而不是因为我在寻找一个实际的应用。

同样，我知道也有人问过类似的问题，但我所看到的帖子中没有一个以我好奇的方式提供任何帮助。

编辑:很抱歉我说得不清楚。那么，让我阐明一条新规则。挑战是找到一种方法来表示无限的斐波那契数列，使用从学习Haskell For Great Good的第一章中尽可能少的额外内容!尽可能这是怎么回事?换句话说，你能想到的最有创意的方法是在尽可能少的"知识"的情况下产生这些数字。很抱歉让大家的回答无效

Answer 1

试试这个:

import Data.List (tails)
fib :: [Integer]
fib = 0 : 1 : [ a + b | (a:b:_) <- tails fib ]

是的，它使用cons操作符(:)作为种子值。但我相信这是可以原谅的。

Answer 2

这当然是可能的，用一个讨厌的技巧:斐波那契数列有一个封闭形式

f

<子> n = (φ;<一口> n - psi; <一口> n )/√5

Prelude> let (φ, ψ) = (1/2+s, 1/2-s) where s = sqrt(5/4)
Prelude> let fibs = [ round $ (φ^n - ψ^n) / sqrt 5 | n <- [0..] ]
Prelude> take 20 fibs
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]

这适用于浮点数，所以它非常快，但不能完全适用于高值:

Prelude> take 3 $ drop 80 fibs
[23416728348467676,37889062373143896,61305790721611584]
Prelude> 23416728348467676 + 37889062373143896 - 61305790721611584
-12

我认为如果不利用无理数或在推导式中加入一些递归，它就不能工作，因为列表推导式只是一元绑定的语法糖，它们本身不是图灵完备的，所以它们不能建设性地生成无限序列。

Answer 3

最简单的当然是:

fibs = f 0 1 where f a b = a : (f b (a+b))

我们从定义中得到这个解。

设f a b计算一个以a开头，b后面的数字流。然后我们可以使用f来计算b之后的子流，如果我们可以计算紧接在b之后的数字。我们知道紧跟在b之后的是a+b，所以我们将该流附加到a。

Answer 4

此解决方案不涉及任何列表库函数，而是使用列表推导式。

fib = [ x | (x,_) <- l ]
   where l = (0,1) : [ (b,a+b) | (a,b) <- l ]