Generating Fibonacci numbers in Haskell?

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?

Thanks.

From stackoverflow

• Here's a simple function that calculates the n'th Fibonacci number:

  fib :: Integer -> Integer
  fib 0 = 1
  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? :)

  Steve B. : I love that - calculate the list by summing the corresponding values of the list you're trying to figure out. My brain doesn't ordinarily work like that - it's like trying to look inside your own ear.

  Christopher Done : `fib 0 = 1` should be `fib 0 = 0`. I only noticed this because I just this second made the same mistake. Haha.

  Yacoby : @Christopher sometimes the first 0 of the sequence is omitted.

  Christopher Done : @Yacoby His definition above is incorrect. fib(0)=0, not 1. This is important. fib(2)=1, the definition above yields fib(2)=2. This is because fib(n) = fib(n-1) + fib(n-2). So, by the above definition, fib(2) = fib(1) + fib(0) = 1 + 1 = 2, which is wrong. This screws up the whole sequence.

  Yacoby : @Christoper No it doesn't. The sequence is just shifted left by 1. Not really a big deal.

• There are a number of different Haskell algorithms for the Fibonacci sequence here. The "naive" implementation looks like what you're after.

• To expand on dtb's answer:

  There is an important difference between the "simple" solution:

  fib 0 = 1
  fib 1 = 1
  fib n = fib (n-1) + fib (n-2)
  

  And the one you specified:

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

  The simple solution takes O(1.618^NN) time to compute the Nth element, while the one you specified takes O(N²). That's because the one you specified takes into account that computing fib n and fib (n-1) (which is required to compute it) share the dependency of fib (n-2), and that it can be computed once for both to save time. O(N²) is for N additions of numbers of O(N) digits.

  yairchu : @newacct: If you only want "fibs !! n", you need to calculative all of "take n fibs", n items, with a calculation of O(n) each because adding two numbers of O(n) digits is O(n).

  Chris Conway : @newacct: You're assuming that every distinct dynamic occurrence of "fib k" (where k is a constant) is merged into a single thunk. GHC might be smart enough to do that in this case, but I don't think it's guaranteed.

  newacct : okay i misread the question. i see that you already said what i was trying to say