Functional sort in C#


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;


    }


}


 


 

Comments (0)