Why Haskell just works

A lot of people experience a curious phenomenon 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 attempts to shed some light on reasons for why that this.

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 mistakes. 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 mistakes. These are more serious mistakes than the silly mistakes, but they are still not due to a misunderstanding of the algorithm.
3. Intentional mistakes. These are mistakes 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, and where it won't.

The fundamental operation of computation in an imperative language is the modification of state. An imperative program consists of an ordered 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 see 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 very little meaningful static checking on the order of statements (and for good reason, it is very hard!). 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. In a purely functional language like Haskell the question of "ordering" is simply not meaningful. The argument should now become apparent: Since the main operation of computation in functional languages (function application) is strongly typed, there's simply less room for errors to sneak in. So the difference, from a static checking standpoint, is that in an imperative language only part of the method of computation is actually checked, whereas for functional languages the entire method of computation can be type checked.

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 accidentally 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 mistake 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 mistake like this. Now, this is a fairly simple example, and naturally most people wouldn't make mistakes in simple examples like this, but hopefully you should be able to see how similar mistakes 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 mistakes 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 mistake 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.

You might claim the the equivalent error to the one used above would be to try to merge list1 and list2 rather than just moving the merge line up a bit, but that's not the case at all. We're talking about a type 2 error here. If the programmer understands the algorithm she will want to merge the sorted lists, not the unsorted lists. In the imperative version the names list1 and list2 both referred to the unsorted and sorted lists depending on where you referenced them, which is the whole root of the problem, whereas in the functional way of thinking only the names sorted_list1 and sorted_list2 refer to the sorted lists.

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 mistakes. These errors are probably caught quite reliably by both imperative and functional programming languages, assuming 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 mistakes. As we saw earlier, this type of mistake 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 mistakes. These are more serious errors, and are hardly ever caught in imperative languages. However, even these mistakes 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 misunderstanding might take the form of an improper ordering of commands which cannot (in general) be caught. Haskell programmers will often testify that while working on a particularly complicated problem the type system helped them spot where their logic was flawed, and once the type errors were fixed so was their understanding.