How to implement the selection sort in Haskell

Overview

Haskell is a functional programming language. The functional programming paradigm 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, the selection sort, in Haskell.

Algorithm

The basic idea behind the selection sort is that we find the minimum element of the unsorted list, place it in the sorted list, and then repeat this process with the remaining list.

We can divide the algorithm into three steps:

  1. Find the minimum element in the list.
  2. Remove the minimum element from the list to get the remaining unsorted list.
  3. Combine the minimum element and the result of the recursive call on the remaining unsorted list.

Example

Let’s translate the above algorithm into a Haskell program:

find_min :: [Int] -> Int
find_min = \list -> 
    case list of
        [] -> error "List cannot be empty!"
        [x] -> x
        x:xs | x > find_min xs -> find_min xs
        x:_ -> x
remove_one :: [Int] -> Int -> [Int]
remove_one = \list -> \v -> 
    case list of 
        [] -> error "Element not found!"
        x:xs | v==x -> xs
        x:xs -> x:remove_one xs v
selection_sort :: [Int] -> [Int]
selection_sort = \list ->
    case list of 
        [] -> []
        _ -> find_min list:selection_sort
                (remove_one list (find_min list))
main = print (selection_sort [8, 9, 3, 4, 7])

Explanation

The find_min function

The find_min() function returns the minimum element in the list.

  • Line 1: The type annotation, find_min :: [Int] -> Int, shows that our function takes a list of integers and returns an integer.
  • Lines 2–3: Next, we have the function definition. It shows that our function takes a list. It is followed by a case expression that implements the recursive formulation of the problem.
  • Lines 4–5: If the list is empty, then we return an error statement. If it contains a single element, then we return that element.
  • Lines 6–7: x:xs in Haskell destructures a list into its head element and the remainder list. The third case statement says that if the head element is greater than the minimum of the remaining list, then return the minimum of the remaining list. Otherwise, we return the head element.

The remove_one function

The remove_one function finds a particular element in a list, removes it, and returns the remaining list.

  • Line 12: The first statement in the case expression shows that if the list is empty, then we throw an error statement.
  • Lines 13–14: For the general case, if the element is equal to the head of the list, we return the remainder of the list xs. Otherwise, we return the list which contains the head of the list. We concatenate it with the list returned by the recursive call to remove_one() which is passed the remainder xs list.

The selection_sort function

Let’s put all the pieces together.

  • Line 19: The first case statement handles the base scenario. If an empty list is passed as input, there is nothing to sort and we return an empty list.
  • Lines 20–21: For the general case, we find the head of the sorted list by calling the find_min function on the unsorted list and concatenate it with the result of a recursive call to selection_sort. The recursive call is passed the unsorted list minus the minimum element by using the remove_one function.
Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)