Haskell is a functional programming language, a programming paradigm that focuses on changing data through expressions that don’t have side effects. These expressions are often called pure functions.
Let’s see how to implement one of the most popular sorting algorithms, Quicksort in Haskell.
The quicksort
function uses the “divide and conquer” technique for sorting:
We choose a pivot element from the list and divide the list into two halves, such that elements less than and equal to the pivot are placed on the left side, and elements greater than the pivot are placed on the right.
We repeat the above process for the resulting left and right subarrays until we end up with a list of size 1.
At this stage, all elements are already sorted, and we combine all the results to return the final sorted list.
Let’s translate the above algorithm into a Haskell program:
-- Return the list which contains elements less than or equal to the input element smallerEq :: Int -> [Int] -> [Int] smallerEq = \v -> \list -> case list of [] -> [] x:xs | x<=v -> x:smallerEq v xs _:xs -> smallerEq v xs -- Return the list which contains elements greater than the specified element greater :: Int -> [Int] -> [Int] greater = \v -> \list -> case list of [] -> [] x:xs | x>v -> x:greater v xs _:xs -> greater v xs -- Sort a list using the quicksort algorithm qsort :: [Int] -> [Int] qsort = \list -> case list of [] -> [] x:xs -> qsort (smallerEq x xs) ++ x:qsort (greater x xs)
smallerEq
functionWe write the smallerEq
function, which returns a list containing elements smaller or equal to the input element.
Line 2: The type annotation, smallerEq :: Int -> [Int] -> [Int]
, shows that our function takes an integer (pivot element) and a list of integers and returns a list of integers.
Line3 to 4: We use the function definition, which shows that our function takes a list and element v
, followed by a case expression that implements the recursive formulation of the problem.
Line 6: x:xs
is a syntax in Haskell that destructures a list into its head element and the remainder list. If the input element is less than or equal to the head element, we return the list x:smallerEq v xs
. This places the head element in the final list and combines it with all the results from the recursive call on the remaining list.
Line 7: The final case statement implements the flip scenario. If the input element is greater than the head element x
, then x
is not part of the final list hence it returns the recursive call smallerEq v xs
, which combines the result from the remaining list.
greater
functionThe greater
function returns a list containing elements greater than the input element. The greater
function is written exactly the same as the smallerEq
function but with the <=
sign replaced with the >
sign. The logic otherwise is the same as above.
quicksort
functionLet’s put all the pieces together.
Line 20: The first case statement implements the base case. If the input list is empty, then there is nothing to sort, and therefore we return an empty list.
Line 21: The second case statement implements the general case. In our quicksort
implementation, we always choose the head element of the list as the pivot. The function call smallerEq x xs
returns the list containing elements smaller or equal to the element x
. Similarly, the function greater x xs
returns the list containing elements smaller or equal to the element x
. We finally call our qsort
function on these resulting lists and we assume our function correctly sorts both the lists. Lastly, we place the x
element in between these sorted lists and concatenate the result to return the final list.
RELATED TAGS
CONTRIBUTOR
View all Courses