在Haskell中生成斐波那契数列？ [英] Generating Fibonacci numbers in Haskell?

问题描述

在Haskell中，如何根据第n个斐波那契数等于第（n-2）个斐波那契数加上第（n-1）个斐波那契数的性质生成斐波纳契数？

$ b

我看过这个：

  fibs :: [Integer] 
 fibs = 1：1：zipWith（+）fibs（tail fibs）
  

我不太明白，或者它如何生成一个无限列表，而不是一个包含3个元素的列表。

我如何编写haskell代码，通过计算实际定义来工作，而不是通过做一些非常奇怪的事情与列表函数？

解决方案

下面是一个简单的函数，计算第n个斐波纳契数：

  fib :: Integer  - >整数
 fib 0 = 0 
 fib 1 = 1 
 fib n = fib（n-1）+ fib（n-2）
  pre> 
 
 
你问题中的函数是这样的： 
 
 
假设你已经有了斐波纳契数列的无限列表数字： 
 
 
  [1,1,2,3,5,8,13 ......] 
  
 
 
 
尾巴是
  [1，2，3，5，8，13，21，....] 
  
 
 $ b 
  zipWith 使用给定的运算符将元素按元素组合在一起：
  [1,1,2,3,5,8,13 ......] 
 + [1,2,3,5， 8，13，21，...] 
 = [2,3,5,8,13,21,34，....] 
   1 和来计算。 1 到使用 +  op将斐波那契数列的无限列表与斐波纳契数列的无限列表的尾部压缩的结果现在，要得到第n个斐波那契数，只需得到斐波纳契数的无穷列表的第n个元素：
 
 
  fib n = fibs !! n 
  
 Haskell的美妙之处在于它不计算Fibonacci数列表中的任何元素，直到它需要。
 
 
 
我的头部爆炸了吗？ ：） 
In Haskell, how can I generate Fibonacci numbers based on the property that the nth Fibonacci number is equal to the (n-2)th Fibonacci number plus the (n-1)th Fibonacci number?

I've seen this:
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
I don't really understand that, or how it produces an infinite list instead of one containing 3 elements.

How would I write haskell code that works by calculating the actual definition and not by doing something really weird with list functions?
解决方案
Here's a simple function that calculates the n'th Fibonacci number:
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
The function in your question works like this:

Assume you already had an infinite list of the Fibonacci numbers:
   [ 1, 1, 2, 3, 5,  8, 13, .... ]
The tail of this list is
   [ 1, 2, 3, 5, 8, 13, 21, .... ]
zipWith combines two lists element by element using the given operator:
   [ 1, 1, 2, 3,  5,  8, 13, .... ]
+  [ 1, 2, 3, 5,  8, 13, 21, .... ]
=  [ 2, 3, 5, 8, 13, 21, 34, .... ]
So the infinite list of Fibonacci numbers can be calculated by prepending the elements 1 and 1 to the result of zipping the infinite list of Fibonacci numbers with the tail of the infinite list of Fibonacci numbers using the + operator.

Now, to get the n'th Fibonacci number, just get the n'th element of the infinite list of Fibonacci numbers:
fib n = fibs !! n
The beauty of Haskell is that it doesn't calculate any element of the list of Fibonacci numbers until its needed.

Did I make your head explode? :)

                        
这篇关于在Haskell中生成斐波那契数列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！