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

问题描述

在 Haskell 中，如何根据第 n 个斐波那契数等于第 (n-2) 个斐波那契数加上第 (n-1) 个斐波那契数的属性生成斐波那契数?

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?

我见过这个:

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

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

I don't really understand that, or how it produces an infinite list instead of one containing 3 elements.

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

How would I write haskell code that works by calculating the actual definition and not by doing something really weird with list functions?

推荐答案

这是一个不同且更简单的函数，用于计算第 n 个斐波那契数:

Here's a different and simpler 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)

您所指的实现基于对斐波那契中的值如何相互关联的一些观察(以及 Haskell 如何根据自身定义数据结构实际上创建无限数据结构)

The implementation you are referring to relays on some observations about how values in Fibonacci relate to each other (and how Haskell can define data structures in terms of themselfs in effect creating infinite data structures)

您问题中的函数是这样工作的:

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, .... ]

这个列表的tail是

   [ 1, 2, 3, 5, 8, 13, 21, .... ]

zipWith 使用给定的运算符逐个元素地组合两个列表:

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, .... ]

因此，可以通过将元素 1 和 1 附加到将斐波那契数的无限列表与使用 + 运算符的无限斐波那契数列.

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.

现在，要获取第 n 个斐波那契数，只需获取无限个斐波那契数列表的第 n 个元素:

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

Haskell 的美妙之处在于它在需要时才计算斐波那契数列中的任何元素.

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屋！