Trusted answers to developer questions

Abdul Monum

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.

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:

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

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])

Sorting list using the selection sort algorithm

`find_min`

functionThe ** 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**: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.`x:xs`

`remove_one`

functionThe ** 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.

`selection_sort`

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.

RELATED TAGS

haskell

communitycreator

sort

selection

CONTRIBUTOR

Abdul Monum

RELATED COURSES

View all Courses

Keep Exploring

Related Courses