C vs. Haskell -- The Pascal Triangle

I recently found a nice example here that points out the level of conciseness that you can get with a Haskell program. The example is about computing the Pascal triangle down to a given depth.

I took the freedom to steal the example, slightly modified, from the above link:

module Main where

next xs = zipWith (+) ([0] ++ xs) (xs ++ [0])
pascal = iterate next [1]

main = mapM_ print $ take 100 $ pascal

It basically says “Take a line (xs), and then add the elements of that line with a 0 added at the left (0 : xs) to the elements of that line with a zero added at the right (xs ++ [0]). The result is the next line.”

Then it takes that rule and applies it to all lines, starting at the line containing only a 1.

That program is very close to the way you actually think about the problem, which is something that is quoted often in the Haskell community as a strong point of the language: it allows you to write things down quite close to how you think about a problem.

The first 10 lines of output look like this:

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]
[1,8,28,56,70,56,28,8,1]
[1,9,36,84,126,126,84,36,9,1]

Just to see how that compares to C, I wrote a straight-forward C version:

#include <stdlib.h>
#include <stdio.h>

typedef unsigned long long int T;

T* allocArray (int size)
{
  return (T*)malloc (size * sizeof(T));
}

void printLine (const T* line, int size)
{
  int i;
  for (i = 0; i < size; ++i)
    {
      printf ("%ld ", line[i]);
    }
}

int main ()
{
  const int depth = 100;

  T** lines;
  int i, j;

  lines = (T**)malloc (depth * sizeof(T*));

  for (i = 0; i < depth; ++i)
    {
      lines[i] = allocArray (i + 1);
    }

  lines[0][0] = 1;

  printLine (lines[0], 1);
  printf ("\n");

  for (i = 1; i < depth; ++i)
    {
      lines[i][0] = 1;
      lines[i][i] = 1;
      for (j = 1; j < i; ++j)
        {
          lines[i][j] = lines[i-1][j-1] + lines[i-1][j];
        }
      printLine (lines[i], i + 1);
      printf ("\n");
    }


  for (i = 0; i < depth; ++i)
    {
      free (lines[i]);
    }

  free (lines);

  exit (1);
}

That also works well enough, but just look at how you get swamped with details: we need to tell the computer how much storage space is needed, we need to allocate that memory, and in the end take care that the memory is released again. In between, there are plenty of chances to introduce errors. In addition, it takes a while when reading the code for the reader to figure out what exactly the code does, and whether it has errors.

In principal, the C version above does not appear to have errors, but there is one: The program does not work, because after a few lines, we get wrong results due to integer overflows. The numbers are just not correct anymore!

The Haskell program, on the other hand, works with the Integer type by default, which is limited in size only by the available system memory. Its result can be assumed to be correct, the program is concise and easy to understand (for someone who knows Haskell syntax, that is — now it’s a good time to go and learn, if you haven’t already!).

I wrote another straight forward version in C++ as well, which is roughly the same size as the C program, and has the same issues minus the explicit memory allocation (it used STL containers).

The run-time turned out to be roughly the same between C and Haskell, with the difference that the Haskell program produces correct results.

Writing the Haskell program took an estimated 1 Minute. Writing the C program took about 10 minutes. After writing the Haskell program, I was pretty sure that it would work, and it did. After writing the C program, I was a little less sure, tested it, saw that it produced a few lines which were correct, and then some with overflows…

Haskell rocks.