Quick sort with a predicate

Question

I want to pass a predicate into quick sort. The issue I'm running into is that the predicate must have two arguments, the pivot and the element of the list's tail. As far as I know though, predicates can only have 1 argument. Here's what I have so far (it runs, I just want to improve it):

import Data.List

quicksort :: [a] -> (a -> a -> Bool) ->  [a]
quicksort [] _ = []
quicksort (x:xs) pf = quicksort left pf ++ [x] ++ quicksort right pf
    where   pred = pf x
            pt = partition pred xs
            left = fst pt
            right = snd pt

Answer 1

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.

Answer 2

To facilitate currying, you should arrange the parameters from the least likely to vary to the most likely to vary. If you put the predicate first, then you could write these partial functions:

ascQuicksort = quicksort (>)
descQuicksort = quicksort (<)

There where clause should be simplified.

import Data.List

quicksort :: (a -> a -> Bool) -> [a] -> [a]
quicksort _ [] = []
quicksort pf (x:xs) = quicksort pf left ++ [x] ++ quicksort pf right
    where (left, right) = partition (pf x) xs

Answer 3

I haven't written Haskell in awhile, so I can't give a great review, but I see something that could be improved on that seems a little backwards to me. You create where bindings for left and right even though you only use each once, but write quicksort * pf twice and don't create a binding for it.

I have a personal love for using local functions to neaten code up, so I'd probably write your code as something closer to:

quicksort :: [a] -> (a -> a -> Bool) ->  [a]
quicksort [] _ = []
quicksort (x:xs) pf = recur (fst pt) ++ [x] ++ recur (snd pt)
    where pred = pf x
          pt = partition pred xs
          recur sub = quicksort sub pf

Using recur, you can remove the duplicate recursing calls. Also, by removing the left and right bindings you can shorten up the where which I personally find cleaner looking.