Here’s a very simple QuickSort algorithm from Wikipedia written in a very Functional way of C#. Notice that it looks very close to the pseudo-code algorithm shown in Wikipedia. The pivot used is just sequence.First(). You can replace the pivot by some random position if you wish.
1: public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> sequence) where T : IComparable<T>
2: {
3: return !sequence.Any()
4: ? sequence
5: : ((from x in sequence.Skip(1)
6: where x.CompareTo(sequence.First()) < 0
7: select x)
8: .QuickSort()
9: ).Concat(new[] { sequence.First() }).Concat((from x in sequence.Skip(1)
10: where x.CompareTo(sequence.First()) >= 0
11: select x).QuickSort());
12: }
I tried making this more fun by using the Fix Point Generator which I mentioned previously, and converted that code into a Func<IEnumerable<T>> instead. Here’s the code.
1: public static Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> F)
2: {
3: return x => F(Fix(F))(x);
4: }
5:
6: static void Main()
7: {
8: var quicksort = Fix<IEnumerable<int>>(
9: qsort =>
10: sequence =>
11: !sequence.Any()
12: ? sequence
13: : qsort(from x in sequence.Skip(1)
14: where x.CompareTo(sequence.First()) < 0
15: select x)
16: .Concat(new[] { sequence.First() })
17: .Concat(qsort(from x in sequence.Skip(1)
18: where x.CompareTo(sequence.First()) >= 0
19: select x)));
20: }
This is a perfect example of how you can use the Fix Point Generator to create your recursive functions on the fly. If you want to make it reusable with an extension method, you can easily convert it to the extension method, or a normal method. Personally I feel that using the Fix Point Generator is more intuitive and slightly more readable as oppose to the extension method way of doing things.
One point to note is that the “Concat” extension only accepts an IEnumerable<T> and not a single item. You can solve this by the above, “new[] { sequence.First() }” which is a cleaner way if you don’t want to write your own extension method (which you could too).
Crazy stuff eh?
