Comments

You could introduce a safeHead function if you really want to be safe:

safeHead :: [a] -> Maybe a safeHead [] = Nothing safeHead (x:xs) = x

Otherwise you have to make sure you never use head on an empty list. Regarding non-empty lists, here's how you'd define them in Haskell:

data Stream a = Cons a (Stream a)

You cannot define functions in Hugs using "let foo x = bar", but you can in GHCi. So if you're using Hugs, you have to define your function in a file or use a "let ... = ... in ..." expression:

> let double x = x + x  in  double 4
8

Regarding ≤ and ≠, yes, they are legal operator names, but no, they are not defined in the Prelude. Here's how you would define ≤:

x ≤ y = x <= y

Or alternatively:

(≤) :: Ord a => a -> a -> Bool
(≤) = (<=)

Here's my ugly attempt at writing a functional qsort in C#. First I'll introduce a pair data structure:

public struct Pair<A, B>
{
    public A First { get; set; }
    public B Second { get; set; }
}

Then a few extension methods:

public static Pair<IEnumerable<T>,IEnumerable<T>>
    Partitions<T>(this IEnumerable<T> xs, Func<T, bool> p)
{
    var partitions =
        (from x in xs
         group x by p(x) into g
         select g).ToDictionary(g => g.Key);
    return new Pair<IEnumerable<T>,IEnumerable<T>>()
    {
        First = partitions.ContainsKey(true)
            ? partitions[true].AsEnumerable() 
            : Enumerable.Empty<T>(),
        Second = partitions.ContainsKey(false) 
            ? partitions[false].AsEnumerable() 
            : Enumerable.Empty<T>()
    };
}
public static bool IsNil<T>(this IEnumerable<T> xs)
{
    return !xs.GetEnumerator().MoveNext();
}
public static bool LessThan<T>(this T x, T y) where T : IComparable<T>
{
    return x.CompareTo(y) < 0;
}

 

Finally, QSort itself:

public static IEnumerable<T> QSort<T>(this IEnumerable<T> xs) where T : IComparable<T>
{
    if (xs.IsNil())
        return Enumerable.Empty<T>();
    else
    {
        var pivot = xs.First();
        var p = xs.Skip(1).Partitions(y => y.LessThan(pivot));
        var smaller = p.First;
        var larger = p.Second;
        return smaller.QSort()
            .Concat(new List<T>{pivot})
            .Concat(larger.QSort());
    }
}

 

Edit: I was bored and also wrote a Python version...

def partition(xs, p):
    z = ([],[])
    for x in xs:
        z[1-bool(p(x))].append(x)
    return z
    # Note that partition is not quite functional, as it uses mutation.
    # The mutation, however, only affects local values. The function
    # partition for the outside world is referential transparent.
def qsort(xs):
    if not xs:
        return []
    else:
        pivot = xs[0]
        smaller, larger = partition(xs[1:], lambda x: x < pivot)
        return qsort(smaller) + [pivot] + qsort(larger)