Haskell for C# 3 Programmers

I've been occupying myself as best I can, waiting impatiently for .NET 3.5 to come out. In the meantime I've been playing with Lisp and Haskell, two of the languages with the most cache among the smart folks who hang out at Lambda the Ultimate. Well it’s happened: I've fallen head over heels for Haskell. It's just so beautiful. It is a pure functional language and is therefore limited in the kinds of operations that can be performed. As a result a little bit of well-thought out syntax to support these operations goes a long way towards improving readability.

It occurs to me that it is worthwhile to introduce C# users to Haskell because many of the improvements coming in C# 3.0 (and many of those introduced in C# 2.0) are actually inspired by Haskell. Learning Haskell is a great way of training yourself to think functionally so you are ready to take full advantage of C# 3.0 when it comes out. There are a variety of Haskell tutorials available on the internet so I will just focus on some similarities between C# and Haskell with the aim of deepening your understanding of both.

Type Inference

Haskell and C# 3.0 both have type inference. In C# 3.0 you write this:
var number = 3;

In Haskell you write this:

number = 3

Haskell’s type inference is a quite a bit smarter than C#'s, but I’ll give you examples of that later.

Lazy evaluation and Streams

In C# I can create a stream of all natural numbers like this:

IEnumerable<int> NaturalNumbers()
{
var i = 0;
while (true){
yield return i;
i++;
}
}

The reason that this loop does not continue forever is that the algorithm stops as soon as a yield command is reached and resumes where it left off when it is started again. In Haskell you can duplicate this behavior by using the colon operator to construct streams.

nat :: [a]
nat = 0 : map (\x -> x +1) nat

This function specifies that the first item in the stream is 0 and then the next result is a list derived from chasing the function's tail and applying a lambda to each item. The map function is equivalent to select in C# 3.0. The first item will be 0, the next will be 1 because the previous was 0, and the next will be 2 because the previous was 1, and so on. The expression on the left side of the colon is an item and the right side is a list. You can build lists like this in Haskell:

0: 1: 2 : 3: 4 : [] -- [] is an empty list in Haskell

This syntax is useful because it signals that the algorithm can stop as soon as it gets a value that it needs, just like yield. It is also very useful to express lists using this colon separated syntax when you are creating recursive list processing functions but I’ll explain that later. For now just make sure you can recognize this syntax as the construction of a list.

Functions, Functions, Functions

It probably won’t come as a shock to you that functional programming relies heavily on functions. Consequently Haskell provides all sorts of useful syntax for manipulating them. The thing that caught me off guard when I first tried to learn Haskell was the function signatures. Look at this example of a function that adds two integers:
add :: Integer -> Integer -> Integer
add x y = x + y
Does this seem odd to you? You might have expected to see something like this:
add :: (Integer, Integer) -> Integer
add (x,y) = x + y

In fact the definition above will work, but it's not really the preferred way of defining functions in Haskell. If you read the first function signature left to right it would say: “add is a function that accepts an integer, which returns a function that accepts an integer, which returns an integer.” One of Haskell's elegant features is that you can take a function that accepts n arguments and convert it into a function that accepts n-1 arguments just by specifying one argument. This is known as partial application. For example given the first add definition I can do this:
addone = add 1 -- returns function that accepts 1 argument

addone 5 -- this returns 6

In Haskell all functions accept a maximum of one argument and return one value. The value returned with be another function with one less parameter until all the arguments have been specified in which case the output value is returned. As I’ll explain later this behavior is very useful when writing certain types of recursive functions.

Recursion

Pure functional languages have no loops. Instead they rely on recursion to repeat operations. Recursive functions have a terminating case and an inductive case. As a result you often see code like this (C#):

public int Add(int x, int y)
{
if (x == 0) // terminating case
return y;
else
return Add(x-1,y+1); // inductive case
}

Haskell allows you to specify the terminating case in a different definition than the inductive case. This is called pattern matching and results in a much more declarative style of coding:


{-- function signature (takes two Nums, returns a Num) --}

add :: Num a => a -> a -> a
add 0 y = y -- terminating case
add x y = (add (x-1) (y+1)) -- inductive case
Take a look at the add function’s signature. add is a generic function. Pretend that "a" is "T" and “Num a =>” is "where T : Num" and it will be a lot clearer. In fact our add function will work on all numeric data types that implement the Num interface (Integer, Double, etc). This doesn’t work in C# because you can’t include operator definitions in an interface. In Haskell, operators are just like any other function and are not bound to a particular class. They just use a symbol instead of a proper identifier. This allows you to include them in interface definitions and thus use them in generic functions.

Now some of you might be asking “Isn’t all this recursion awfully expensive?” No, because Haskell and many other functional languages are equipped to recognize a particular kind of recursion known as tail recursion. When Haskell recognizes this type of recursion it translates it into a simple loop so that the stack doesn’t grow. For instance our C# version of Add above could be translated to the following by a smart compiler:

public int Add(int x, int y)
{
do {
if (x == 0) // terminating case
return y;
else
{
x = x-1;
y = y+1;
}
} while(true);
}

So how do you tell when a function is tail recursive or not? It’s easy. If a function ends with a call to the same function it is tail recursive. The add function defined above is tail recursive because at the end of function add is called again. Some functions are not tail recursive which means they do grow the stack. Take the following flatten function which takes a list of lists and flattens it into a list:


flatten :: [[a]] -> [a]
flatten [] = [] –- if list is empty, return empty list
flatten (y:ys) = y ++ (flatten ys)


Notice that the last operation to execute is the list concatenation (++) function. This means that the concatenation function must wait for a result from the recursive call to flatten before it can finish its computation. As a result flatten will consume both time and stack space because it will have to keep track of where we are in each previous recursive call.

The good news is that we can take many recursive functions and convert them into tail recursive functions using a straightforward technique. We introduce an accumulator function that adds a new parameter and uses it like a variable to store the computation done so far.

flattenAcc :: [a] -> [[a]] -> [a]
flattenAcc acc [] = acc
flattenAcc acc (y:ys) = flattenAcc (acc ++ y) ys

flatten = flattenAcc [] –-partial application

I want you to notice that we are using the colon list syntax in the inductive case definition of flattenAcc. This is a great example of pattern matching. We are effectively saying that in this version of flattenAcc y represents the first item in the list passed as the second parameter and ys represents the rest of that list. Haskell uses its own syntax in its pattern matching expressions resulting in very readable code.

In our revised version the last procedure called in flattenAcc is flattenAcc. This makes our function tail recursive. In order to accomplish this flattenAcc effectively stores the state of the flattened list so far in the newly introduced "acc" function parameter. Remember that when a tail recursive function get translated into a loop the function parameters act like variables. Note that we don’t need to specify a type signature for flatten because Haskell infers it.

*Note: Derek Elkins and Cale Gibbard point out in the comments that tail recursive functions are not always preferable to recursive ones because of Haskell's lazy evaluation. If you can write a non-recursive function that uses the colon syntax it is probably better than a tail recursive one that doesn't. This is because Haskell's lazy evaluation enabled you to use the non-tail recursive version on an infinite stream without getting a stack overflow.
Now you’re familiar with the basic concepts of functional programming. Next time we’ll look at features that inspired C# query comprehensions and nullable types.