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