Lazy Fibonacci

OK, maybe I’m not quite done with computing Fibonacci numbers. I’ve been playing around a bit with Haskell lately. Here’s what the Haskell equivalent of the C code I posted earlier is:

module Main where
import Control.Exception as C
import System.Environment
import System.IO
fibonacci = 0 : 1 : zipWith (+) fibonacci (drop 1 fibonacci)
main = do argv <- getArgs
          name <- getProgName
          if not (null argv)
                then let which = head argv
                         result = fibonacci !! read which
                     in (putStr $ "Fibonacci number #" ++ which ++ " is " ++ (show result) ++ "\n")
                                `C.catch` (\_ -> hPutStr stderr "Must give a nonnegative integer\n")
                else hPutStr stderr $ "usage: " ++ name ++ " number\n"

Most of the volume there is trying to mimic the same error handling I was doing in the C code in main. However, the code that computes Fibonacci numbers is much shorter. In C, I had to write a whole function. In Haskell, it’s a one-liner. Here it is again:

fibonacci = 0 : 1 : zipWith (+) fibonacci (drop 1 fibonacci)

If you haven’t been exposed to Haskell before, that might make your head explode. Note that it isn’t a function at all. It’s a list of all Fibonacci numbers.

Yes, the Fibonacci sequence is infinitely long. Haskell is fine with that.

Yes, my definition is recursive. Haskell is also fine with that.

This works because Haskell is lazy: it only computes things at the point when the result of the computation is actually used. At runtime, it only actually computes the elements of the list up to the one that’s requested by the user, instead of trying to create an infinitely large list and then indexing into it. That’s also why the recursive definition works: each element is defined solely in terms of the elements that come before it, and I provide the first two elements explicitly.

Specifically, what’s going on in that line is this. zipWith takes two lists, performs an operation on pairs of elements taken from each list, and returns a list of the result of that operation. Here, the operation is (+), plain old addition. The two lists are the Fibonacci sequence we’re defining (fibonacci), and the Fibonacci sequence with the first element dropped off (drop 1 fibonacci).

For example, the first element produced by the zipWith expression takes the first element from fibonacci, which is 0, and the first element from drop 1 fibonacci, which is 1, adds them together to get 1, and returns that as the third element of fibonacci. For the fourth element, it takes 1 and 1 and returns 2. For the fifth element, it takes 1 and 2 and returns 3. And so on, as long as it needs to.

For the visually inclined, try this:

   0   1   1   2   3   5   8  13  21  34  ...   (fibonacci)
+  1   1   2   3   5   8  13  21  34  55  ...   (drop 1 fibonacci)
   1   2   3   5   8  13  21  34  55  89  ...   (drop 2 fibonacci)

Infinite lists aren’t unusual in Haskell. In fact, the standard library (called the Prelude), has several functions designed to help you create infinite lists.

Needless to say, trying to do this in a non-lazy language is a recipe for disaster. Your program will run until either the heat death of the universe or it runs out of memory (whichever comes first) building the infinite list and will never get around to actually using it.

This is at the core of why it’s worth studying other programming languages, even if you don’t expect to use them. You can often learn new ways to look at problems that you’d never even consider if you stick with a single language. No C programmer would ever compute Fibonacci numbers by constructing a list of all of them, but in Haskell, it’s downright natural.