advanced code snippet search

Posted By

rtperson on 06/01/11


Tagged

fibonacci


Versions (?)

Fibonacci List One-Liner in Haskell

 / Published in: Haskell
 

URL: http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

I didn't invent this, but it's too cool a snippet not to capture. Here's a one-liner that will generate a list of Fibonacci numbers in linear time.

EXPLANATION: the colon operator is used to add elements to a list, so it starts out adding on the two base cases, zero and one. After you have these two, you can mathematically generate the rest of the list. The zipWith function takes two lists and combines them using a function (in this case, addition). The two lists in question are fiblist (that is, the list you're currently generating) and "tail fiblist" (that is, every element of the list after the first element).

The only reason this works is because Haskell's laziness gives it the ability to define infinite lists. Haskell will never even attempt to calculate the nth Fibonacci number until it is asked to do so.

Expand | Embed | Plain Text 
  1. fiblist = 0 : 1 : zipWith (+) fiblist (tail fiblist)
  2.  
  3. -- you can access members of this list as follows: 
  4. -- fiblist !! 10
  5. -- (returns 55)
  6. -- fiblist !! 100
  7. -- returns 354224848179261915075

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: deepsoul on July 11, 2011

You did not mention the most remarkable thing about this: It avoids computing each element many times, as a naive recursive implementation would. This is because Haskell memoizes (caches) constant definitions.

You need to login to post a comment.