As 200 said, the predicate should be first. Think of filter
, takeWhile
, dropWhile
and similar functions. They take the predicate first.
Also, it's usually a good idea to get rid of arguments that get repeated in every recursive call. GHC should take care of that, but we can help it a little bit:
quicksort :: (a -> a -> Bool) -> [a] -> [a]
quicksort pf = go
where
go [] = []
go (x:xs) = go left ++ [x] ++ go right
where (left, right) = partition (comp x) xs
However, we're sorting. Therefore calling the comparison function a predicate is a misnomer. A predicate is a function a -> Bool
, whereas a -> a -> Bool
is a comparison. But a -> a -> Bool
doesn't convey its meaning by its type. Do we return True
if the first shall come first in the sorted arrangement? Or do we return False
? Will quickSort (>)
sort ascending or descending?
Those questions are easier to answer if we use a -> a -> Ord
instead. This signature follows compare
's, so we have a pretty good feeling what x `compare` y = LT
means, namely that x < y
holds true.
If we keep that in mind, we can write the following variants:
quicksortBy :: (a -> a -> Ord) -> [a] -> [a]
quicksortBy comp = go
where
go [] = []
go (x:xs) = go lesser ++ (x : equal) ++ go greater
where
(lesser, equal, greater) = partitionOrd (`comp` x) xs
quicksort :: Ord a => [a] -> [a]
quicksort = quicksortBy compare
The definition of partitionOrd :: (a -> Ord) -> [a] -> ([a], [a], [a])
is left as an exercise. Other than that, well done. Keep in mind that this isn't really Quicksort, though.