Naive Haskell implementation of Quick Sort.

quick-sort.hs

--------------------------------------------------------------------------------
import Data.Function ((&))
--------------------------------------------------------------------------------
import qualified Data.List as List
--------------------------------------------------------------------------------
main :: IO ()
main =
  [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] & quickSort & show & putStrLn

-- | FP implementation of QuickSort. Intended as an exercise in a high-level
-- understanding of the QuickSort algorithm.
quickSort :: (Ord a) => [a] -> [a]
quickSort []  = []
quickSort [x] = [x]
quickSort xs  = quickSort lhs <> [pivot] <> quickSort rhs
  where
    (pivot, rest) = pivotFor xs
    (lhs, _, rhs) = partition pivot rest

-- | Note: partitioning does not happen in-place as it should canonically
partition :: (Ord a) => a -> [a] -> ([a], a, [a])
partition pivot xs = (lhs, pivot, rhs)
  where
    (lhs, rhs) = List.partition (< pivot) xs

-- | Naive pivot function that just selects the leftmost element as the pivot
pivotFor :: [a] -> (a, [a])
pivotFor (x:rest) = (x, rest)