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.

9 Responses

  1. If there’s anything I learned last summer, its that computers and infinity don’t mix, but apparently they can hang out.
    This little though experiment may be useful when working with elliptic curves, but its 2am….

    Though if you’re computing Fibonacci numbers wouldn’t it be a lot more efficient use the formula involving the golden ratio?

    Now I want to try something with chinese remainder and fibonacci numbers, but its still 2am…

  2. Depending on the application, the closed form equation may not be more efficient, especially if (like the Haskell solution) you’re saving a copy of your results for later use. If your list of Fibonacci numbers is in the processor’s cache, it’s possibly faster to look something up in the list than it is to do some floating point operations. Of course, you’d need to actually profile the code to see if that’s truly the case on your target system.

    Having said that, I can’t recall ever running into a program that needed to compute Fibonacci numbers where the problem to be solved wasn’t explicitly “compute Fibonacci numbers.”

  3. So I kinda wondered about using CRT and found this little undergrad project:

    http://www.math.oregonstate.edu/~math_reu/Proceedings/2003/AM_Final.pdf

    Looks like the computations are significantly faster, though I guess they don’t precisely use CRT in the end. I didn’t really read a lot of it, and you could be using that method. I just like that my intuition to use CRT kind of worked out.

  4. The Haskell code is just using the standard definition of Fibonacci numbers; it’s just written in a way that’s not immediately obvious.

    Fun math fact about Haskell: its input/output mechanism is based around monads, which are adapted from category theory. Once I wrap my head a little better around monads in Haskell I’ll probably do a post or two on them, since it is kind of neat once it all clicks together.

  5. This is cool! (monads?)

  6. Frickin’ monads.

  7. Welcome to the functional party,

    You are probably not writing in a Haskell-y enough syntax

    This feels better syntax to me:

    main = do argv <- getArgs
    name hPutStr stderr $ “usage: ” ++ name ++ ” number\n”
    x:xs -> C.catch (putStr $ “Fibonacci number #” ++ x ++ ” is ” ++ (show result) ++ “\n”)
    (\_ -> hPutStr stderr “Must give a nonnegative integer\n”)
    where result = fibonacci !! read x

    Ideally I would also remove the catch clause and make better use of the Either datatype

  8. Welcome to the functional party,

    You are probably not writing in a Haskell-y enough syntax

    This feels better syntax to me:

    main = do argv <- getArgs
    name hPutStr stderr $ "usage: " ++ name ++ " number\n"
    x:xs -> C.catch (putStr $ "Fibonacci number #" ++ x ++ " is " ++ (show result) ++ "\n")
    (\_ -> hPutStr stderr "Must give a nonnegative integer\n")
    where result = fibonacci !! read x

    Ideally I would also remove the catch clause and make better use of the Either datatype

  9. Is there something in that code that’s getting garbled by WordPress?

Comments are closed.