## Wednesday, January 20, 2010

I'm usually pretty enamored with Python, but I think Haskell has it beat when it comes to generating the Fibonacci sequence. The most obvious way to write the Fibonacci sequence in Python is with a generator.

def fib():
x,y = 0,1
while True:
yield x
x,y = y, x+y

Hasekll, in contrast, uses a lazily evaluated list. At first I thought of such a list as a generator, but when I saw this example I realized that the lazy list was a lot more powerful.

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

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

In Haskell, 0 : 1 : 2 : 3 is equivalent to [0, 1, 2, 3]: it generates a new list. In this case, you're starting with [0, 1], then adding more stuff to the end. In the first example, it's a list comprehension, approximately equivalent to [a+b for (a, b) in zip(fibs, fibs[1:])] in Python. However, you can't build a succint one-liner like this in Python because fibs has to be defined before you can iterate over it. In Haskell, you start with a short list and build the rest of it implicitly.

The second line is even cooler. Instead of going through the trouble of defining a list comprehension, you just use zipWith. This would be equivalent to the following Python snippet:

def zip_with(function, sequence1, sequence2):
return [function(item1, item2) for item1, item2 in zip(sequence1, sequence2)]

This is a great example of how carefully chosen higher-order functions can simplify your code. When I first started using list comprehensions in Python, I was doing things like [str(i) for i in xrange(10)] all the time, when it's much more clear and succint to use map(str, xrange(10)).