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).)

2006-12-01 11:04:45 · 6 comments
  

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

  1. Pete
    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. dons
    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. Pete
    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 ... ]

Leave a reply

You can use HTML, but you don't have to. Formatting tips (for code, quotes, etc.) here.