Why Haskell just works

A lot of people experience a curious phenomena when they start using Haskell: Once your code compiles it usually works. This does not seem to be the case for imperative languages, not even strongly typed ones like Java or C#. This page tries to explain why this seems to be the case.

Types of Errors

There are many types of errors, and many ways to categorize them. For our purposes we shall categorize them in the following way:

1. Silly misstakes. These include things like typos, or just forgetting some minor thing here and there. Many of these would be caught by the type checker, or even the parser, though some might slip through.
2. Unintentional misstakes. These are more serious misstakes than the silly misstakes, but they are still not due to a misunderstanding of the algorithm.
3. Intentional misstakes. These are misstakes which are simply the result of not understanding the algorithm. The programmer really did intend for the program to do what it does, the fact that it is not correct is due to the programmer not understanding the algorithm.

The important distinction here is between the two latter types. Some will tend to think that these are actually the same category. In other words, if your code compiles but doesn't work, it's the programmer's fault. This is true to some extent, but it is also true that this very often happens even though the programmer has a firm understanding of the algorithm she is trying to implement, so the distinction is important.

We will return to this categorization of errors later on in the discussion.

The Method of Computation

There is an important difference in how computation is performed in imperative and functional languages. We shall first look at a strongly typed imperative language, and try to reason about how and where static checking might help to prevent errors.

The fundamental operation of computation in an imperative language is the modification of state. An imperative program consists of an orderered sequence of state modifying commands. This is of course only true to some extent, since you can often use a functional style even in an imperative programming language, but in general the computations are performed primarily by modifying state. The important realisation here is that the result of a computation is not actually specified directly in an imperative programming language, but is extracted indirectly as a side effect of executing the state modifying commands. From this we follows the result of an imperative computation depends on two things; the stateful commands, and the order in which these are executed. Of these two things only the former can be statically checked. Imperative languages in use today do no meaningful static checking on the order of statements in an imperative language. This is the key to why plenty of programs which compile just fine in a strongly typed imperative language, simply don't work properly at all; the static checking performed by the compiler can only catch a very small fraction of the errors that are possible.

Functional programming is quite different. Here the fundamental operation of computation is function application. The argument should now become apparent: Since function application is strongly typed, there's simply less room for errors to sneak in.

Let's do an example. We'll write this in a fictional strongly typed imperative language, first using an imperative style, and then using a functional style. We don't use actual languages to better highlight the differences between the two versions. As a simple example we shall implement a part of a merge sort algorithm. We assume here that a function, merge, is available which will merge two sorted lists into one sorted list (for two unsorted list it will simply produce the wrong result).

list.sort() {

 if ( self.size <= 1 ) 
 {
     return;
 }
 (list1,list2) = self.split( self.size / 2 );
 
 list1.sort();
 list2.sort();
 merged_list = merge( list1, list2 )
 self.set( merged_list )

}

For the sake of argument, let's assume that the programmer accidently reordered the lines here, maybe she merges the lists before they are sorted, for example. A type 2 error. It's clear that such a misstake would mean the sorting routine won't produce the correct result, however it is also clear that the compiler won't be able to catch a misstake like this. Now, this is a fairly simple example, and naturally most people wouldn't make misstakes in simple examples like this, but hopefully you should be able to see how similar misstakes which are far less obvious and far easier to make are very common in imperative programming.

The key idea, yet again, is that the result of the computation depends not only on the stateful operations themselves, but also the order in which they are executed. Only the former of these two aspects can actually be statically checked. It is clear that misstakes due to the order of operations can in general not be caught by the compiler, and this leads to many faulty programs that nonetheless compile happily.

Let's rewrite the same thing in a more functional style. I should stress that this is not Haskell code, but the same made up pseudo language used above.

list.sort() : list {

 if ( self.size <= 1 ) 
 {
     return self;
 }
 (list1,list2) = self.split( self.size / 2 );
 
 sorted_list1 = list1.sort();
 sorted_list2 = list2.sort();
 merged_list = merge( sorted_list1, sorted_list2 )
 return merged_list

}

Notice that we only changed some minor things here. Most importantly the sort method no longer changes any state, it simply returns a new sorted list (rather than changing the current one in place).

By switching to a functional approach we now see that the algorithm is expressed directly in the code, rather than indirectly as a product of stateful operations and their uncheckable ordering. If you were to make the same misstake in this code, trying to perform the merge before the sorts, you would get a compile time error. This is because the lists used in the merge, depends on the lists retrieved from the split, which depends on the list we're trying to sort. So you see that the "ordering" is made explicit and direct, and will be statically checked at every stage.

Type of Errors Caught at Compile time

We saw in the previous section that simply by switching to a different way of thinking we were able to catch a type 2 error at compile time, while this was impossible when using the imperative method. Let's discuss the three types of errors again, in some detail.

1. Silly misstakes. These errors are probably caught quite reliably by both imperative and functional programming langauges, assume they have a sane language design and strong typing. For this category of errors the property of being functional or imperative is probably less important than other properties.
2. Unintentional misstakes. As we saw earlier, this type of misstake can quite often slide through the compiler's checks in an imperative language since for imperative code the important property of ordering is not checked. We also saw how this problem is helped by using a functional style together with static type checking. The fact that functional programming catches these errors while imperative programming does not, is probably largely the reason for why Haskell programs tend to "just work".
3. Intentional misstakes. These are more serious errors, and are hardly ever caught in imperative languages. However, even these misstakes are often caught by functional programming languages for the same reason that errors of type 2 are. If you've misunderstood the algorithm, it is very likely that this will result in some type error when expressing it in a functional style, whereas if it is expressed in an imperative style the misunderstaning might take the form of an inproper ordering of commands which cannot (in general) be caught.