Explaining Quicksort in Haskell line by line


Sat Dec 28 2019 19:50:17 GMT+0000 (Coordinated Universal Time)

Saved by @divisionjava #haskell #interesting #functionalprogramming #quicksort #elegantcode

quicksort :: Ord a => [a] -> [a] 
quicksort [] = [] 
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) 
     lesser = filter (< p) xs 
     greater = filter (>= p) xs

Line 1: The function's type signature: it says that quicksort transforms a list of elements of some type a (usually read "alpha") into a list of the same type, for a type a that is an instance of typeclass Ord (which means that comparison operations are defined for it, so elements of type a can be compared with one another). Line 2: The result of sorting an empty list is an empty list. Line 3: p is the first element. The rest of the list if xs. The function defines that all elements be sorted kh n the order of "lesser" in increasing order (denoted by ++), followed by p, and then "greater". Lines 4-6: Define which elements are lesser and greater. Lines 5 states all elements in xs that are less than p are "lesser" while line 6 says that p and all elements greater than it are "greater"