Generating Fibonacci numbers in Haskell?

by

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)

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

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? 🙂

More Related Contents:

  1. How is this fibonacci-function memoized?
  2. `String’ is applied to too many type arguments
  3. How do I define Lisp’s apply in Haskell?
  4. Operating on a return from a Maybe that contains “Just”
  5. Is there a Haskell idiom for updating a nested data structure?
  6. What’s so bad about Lazy I/O?
  7. Positive integer type
  8. Explicitly import instances
  9. How to compare two functions for equivalence, as in (λx.2*x) == (λx.x+x)?
  10. Why do 3 and x (which was assigned 3) have different inferred types in Haskell? [duplicate]
  11. How do I use fix, and how does it work?
  12. Splitting list into a list of possible tuples
  13. What is the purpose of the reader monad?
  14. Haskell: I/O and Returning From a Function
  15. Ordering of parameters to make use of currying
  16. No instance for (Fractional Int) arising from a use of `/’
  17. Type Constraints in Data Declaration Haskell
  18. Prefix form of unary operator in Haskell
  19. How can I generate different random values in Haskell?
  20. Can you overload + in haskell?
  21. Non-Trivial Lazy Evaluation
  22. Is there a way to see the list of functions in a module, in GHCI?
  23. Haskell GHC: what is the time complexity of a pattern match with N constructors?
  24. Creating unique labels in Haskell
  25. What’s the status of multicore programming in Haskell?
  26. Tools for analyzing performance of a Haskell program
  27. Haskell Constraint is no smaller than the instance head
  28. Can I match a data constructor wildcard in Haskell?
  29. Is there, in Haskell, something similar to sub-guards?
  30. What is the Comonad typeclass in Haskell?

Leave a Comment