# 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.

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.

```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

```

### One Response to Exploring Functional Programming with Erik Meijer and Haskell

1. miniBill says:

This code will enumerate its input multiple times. This is suboptimal.