Fibonacci series one-liner in Haskell

Here’s a beautiful example of why Haskell is the most advanced programming language on the planet – a one-line definition of the entire fibonacci series:

fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist))

Stunning. Note that that is not a function to calculate the nth fibonacci number: it really is a definition of the entire series. If you want the nth fibonacci number, look up the nth element of that list. Let’s see you do that in Java! (Or C#)

(Via the introductory series on Haskell at the rather good Good Math, Bad Math (more on the author here).)

7 Responses to “Fibonacci series one-liner in Haskell”

  1. December 3rd, 2006 | 4:21 pm

    I was going to post a really long comment, but I decided to put it on my blog instead.

  2. December 8th, 2006 | 4:13 am

    Cultural note: coding up the fibonacci series is a standard greeting for newcomers in
    #haskell For example:

    > fix ((1:) . scanl (+) 1)
    
    > let fibs = 1 : scanl (+) 1 fibs in fibs
    
    > let fibs = 1 : 1 : zipWith (+) fibs (tail fibs) in fibs
     
    > fix $ \fibs -> 1 : 1 : zipWith (+) fibs (tail fibs)
    
    > let  fib@(1:tfib) = 1 : 1 : [ a+b | (a,b)  let fibs = 1 : 1 : (zipWith (+) `ap` tail) fibs in fibs

    :-)

  3. December 13th, 2006 | 1:24 am

    I presume for the second to last one you mean:

    > let fib@(1:tfib) = 1 : 1 : [ a+b | (a,b) <- zip fib tfib ] in fib
    

    Which is more or less equivalent (in terms of how it works) to the zipWith implementation. I got caught out with the < too – you have to html-escape it. (More “must use HTML” than “may use HTML” really :)

    Edit 2007.01.21 — not any more! -gimbo

  4. Dave
    May 2nd, 2008 | 4:46 am

    Same thing but in scheme

    
    
    ; Lazy lists in Scheme
    
    ;; Top of the stream
    (define head car)
    
    ;; Rest of the stream
    (define tail 
      (lambda (stream) (force (cdr stream))))
    
    ;; Define zipWith to zip two streams with a function to produce a list.
    (define zipWith
      (lambda (f s1 s2)
        (letrec ((generate 
    	      (lambda (s1p s2p)
    		(cons (f (head s1p) (head s2p)) (delay (call-with-values 
    						(lambda () (tails s1p s2p))
    					      (lambda (a b) (generate a b)))))))
    					      
    	     (tails
    	      (lambda (s1p s2p)
    		 (values (force (cdr s1p)) (force (cdr s2p))))))
          (generate s1 s2))))
    
    
    ;; builds a fibonacci stream
    (define fibonacci-stream
      (letrec ((generate 
    	    (lambda ()
    	      (cons 0 (cons 1 (delay (zipWith + fibonacci-stream (tail fibonacci-stream))))))))
        (generate)))
    
    ;; Builds a list from a stream n items long
    (define take
      (lambda (n stream)
        (letrec ((builder 
    	      (lambda (accum n stream)
    		(cond 
    		 ((equal? 1 n) (cons (head stream) accum))
    		 (#t (builder (cons (head stream) accum) (- n 1) (tail stream)))))))
          (reverse (builder '() n stream)))))
     
    ;; Drops items from a stream
    (define drop
      (lambda (n stream)
        (cond
         ((equal? 0 n) stream)
         (#t (drop (- n 1) (tail stream))))))
    
    

  5. nikolao
    October 22nd, 2008 | 6:00 pm

    Here it is in Perl 6:

    my @fiblist = 0, 1 ... { $^a + $^b };

  6. mykelyk
    November 12th, 2008 | 12:17 pm

    
    f=scanl(+)1f -- golfed to 12 chr -> [1,1,2,3 ... ]
    

  7. July 23rd, 2010 | 5:01 pm

    The Perl 6 example from 2008 is now out of date. Here’s an updated version.

    
    0, 1, { $^a + $^b } ... *
    

    Or you could make it a little more concise:

    
    0, 1, * + * ... *
    

    And if you want to golf it:

    
    0,1,*+*...*  # 11 characters