Exploring Functional Programming with Erik Meijer and Haskell

Erik Meijer of Microsoft Research is an inspiring guy and his work on LINQ is impressive. I just stumbled across his lecture series on exploring Functional Programming Fundamentals and I decided I would do the course and learn Haskell. I want to expand my frame of reference from primarily imperative and relational thinking to functional thinking. I like the idea of starting with Haskell instead of something like F# simply because Haskell is designed as a pure functional language for teaching and research. Working with Haskell sets aside the complexity of integrating huge a huge framework library.

The text that Dr. Meijer is using is Graham Hutton’s Programming in Haskell which is conveniently available at a discount on Kindle. Hutton’s text uses the Hugs98 Haskell interpreter which is available from haskell.org but seems to have been unmaintained since 2006. The Haskell Platform is also available from haskell.org and is prominently linked on the haskell.org home page. The Haskell Platform is “batteries included’ (ala Python) and based on the Glasgow Haskell Compiler (GHC) and interpreter (GHCi). It seems like GHCi is equivalent to Hugs and works in the same way.

A quick aside here. The maintainer of GHC, Simon Peyton Jones, is also a fellow at Microsoft Research. Interesting.

Homework: Transliterate QuickSort from Haskell C#

OK. I’ve read the first chapter of Hutton and watched the first lecture from Dr. Meijer. In addition to the exercises in Hutton’s text, Dr. Meijer suggested a homework problem of transliterating the Haskell qsort example into C# using LINQ.

Here’s my implementation.

QuickSort in Haskell

qsort []     = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
                where
                    smaller = [a|a <- xs, a <= x]
                    larger = [b|b <- xs, b > x]

QuickSort in C# with LINQ extension methods

The C# version is more verbose primarily because of some of the Haskell syntactic sugar, like the ++ operator for concatenating lists and the sort of function overloading in Haskell:

• f [] = [] means that when an empty list is the input of function, f, then an empty list is the output.
• f (x:xs) automagically takes the first element of the list an puts it into x while the remainder is in xs.

Also, Haskell implicitly knows that types are comparable whereas in C# I have to do some gross syntax with generic constraints an explicitly use IEnumerable<T>.CompareTo(T). Other than those syntactic differences, the C# version works essentially the same way as the Haskell version.

using System;
using System.Collections.Generic;
using System.Linq;

namespace QuickSort
{
    static class Program
    {
        static void Main( string[] args )
        {
            var t = new [] { 3, 5, 1, 4, 2 };
            Console.WriteLine( string.Join( ", ", t.QuickSort().ToArray() ) );
        }

        //this does not do the sort in place, but neither did the Haskell version
        public static IEnumerable<T> QuickSort<T>( this IEnumerable<T> list ) where T : IComparable<T>
        {
            //qsort [] = []
            if( list.Count() == 0 )
            { return list; }

            //qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
            var x  = list.First();
            var xs = list.Skip( 1 );

            return QuickSort( xs.Where( a => a.CompareTo( x ) <= 0 ) )
                    .Concat( new[] { x } )
                    .Concat( QuickSort( xs.Where( a => a.CompareTo( x ) > 0 ) ) );
        }
    }
}

PS> csc -nologo Program.cs; ./program
1, 2, 3, 4, 5