November 14th, 2009

run the fuck away

Haskell - Programming Language

I've been hearing all sorts of stuff about Haskell lately. It's a programming language that has all of my favorite features: it's a functional language, it uses pattern matching on function definitions, and it's got a very sparse, simple, syntax.

While it doesn't have quite the rarefied elegance of LISP, it has one other really fantastic feature: it uses lazy evaluation all the time. In contrast, pretty much every other language uses eager evaluation most of the time.

For example, if I did this in pretty much any language:
x = 2 * 2
It would execute 2 * 2 and put the result into x. This is eager evaluation. In Haskell, on the other hand, it doesn't execute anything, it just creates what's called a "thunk" and says, "hey, if anybody ever wants to know what's in x, tell them it's 2 * 2. I won't figure out what 2 * 2 is until someone actually wants to know what's in x."

This has some weird effects. For one, you never know precisely when a line of Haskell code is going to execute. It doesn't execute code in order, only as needed. Some code will never execute, because Haskell never decides it needs the results of that expression. And because of all that, you can do something in Haskell that you can't do in most languages: create infinitely long data structures.

For example, I could define a function like this in Haskell:
makeList n = n : makeList (n + 1)

That defines a function called makeList that takes one parameter (n). After the "=", it explains what it does: take n, and construct a list (:) with the result of calling makeList on the value n + 1. If I invoked makeList 0, it would return a list like this: [0,1,2,3,4...∞].

Obviously, it's impossible to create an infinitely long list, but since Haskell doesn't actually evaluate the list, I can actually call makeList 0 and get back a thunk capable of producing an infinitely long list.

But it gets better- since the function is recursive, Haskell can execute any arbitrary number of recursions without needing to produce the entire list. So, for example, if I wanted to get all of the list after the first element, I could write this statement:
tail (makeList 0)

That returns a list containing all integers from 1 on up. And if I wanted the 1,000,000th number in that list? I could actually grab it, and Haskell would execute up to that number, and no more.

I can understand why mathematicians like this language. It's the first one that has a really good grasp of how to handle infinities.

*This is not the most elegant way to write an infinite list in Haskell. Much more easily, I could write: [1,2,..]. [1,2,..] !! 1000000 would return the 1,000,000 element of the list (the number 1,000,000 in this case).