Share via

Functional sort in C#

  • Article

On an internal mailing list, we were discussing functional languages, and this Haskell sort code:

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

While trying to explain how this code works (which is very different from what it looks like to C++/C# programmers due to lazy evaluation) I've come up with following C# code (with Linq) that is logically similar to Haskell version. Obviously, Haskell code is much nicer though.

static IEnumerable<T> Qsort<T>(IEnumerable<T> s) where T : IComparable<T>

{

    IEnumerator<T> e = s.GetEnumerator();

    if (e.MoveNext())

    {

        T x = e.Current;

        foreach (T t in Qsort(s.Skip(1).Where(y => y.CompareTo(x) < 0)))

            yield return t;

        yield return x;

        foreach (T t in Qsort(s.Skip(1).Where(y => y.CompareTo(x) >= 0)))

            yield return t;

    }

}