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 insertion sort, in Haskell.

The basic idea behind **insertion sort** is that we repeatedly place each unsorted element in its correct place so that we end up with a sorted list.

We can divide the algorithm into two parts:

- Insert a new element in a sorted list in its correct place.
- Repeate the above process on each element of the input list recursively to get the final sorted list.

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

insert_sorted :: [Int] -> Int -> [Int] insert_sorted = \list -> \v -> case list of x:xs | v>x -> x:insert_sorted xs v _ -> v:list insertion_sort :: [Int] -> [Int] insertion_sort = \list -> case list of [] -> [] x:xs -> insert_sorted (insertion_sort xs) x main = print (insertion_sort [8, 9, 3, 4, 7])

Sorting list using the insertion sort algorithm

`insert_sorted`

functionThe ** insert_sorted function** inserts a new element in a sorted list in its correct place.

**Line 1**: The type annotation`insert_sorted :: [Int] -> Int -> [Int]`

shows that our function takes a list of integers, an integer element that needs to be inserted, and returns the resultant list.**Lines 2–3**: Next, we have the function definition that shows that our function takes a list, an integer element`v`

, followed by a case expression that implements the recursive formulation of the problem.**Line 4**:`x:xs`

in the case statement is a syntax in Haskell that destructures a list into its head element and the remainder list.**Line 5**: We compare the input element with the head of the list. If the input element is greater, we must traverse the remaining list. Therefore, we return the list with the head of the original list concatenated with the result of the recursive call to the`insert_sorted`

function which is now passed the remainder of the list`xs`

. In the second case statement, we check if the input element is less than the head element, and then place the input element at the beginning of the list.

`insertion_sort`

functionLet’s put all the pieces together.

**Line 9**: 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.**Line 10–11**: For the general case, we recursively call the`insertion_sort`

function. We pass it`xs`

, the list with its head removed. We can assume that our function correctly sorts the list`xs`

. The`insert_sorted`

function determines the correct place of the unsorted head element in the sorted list returned by the recursive call. We return the list returned by the`insert_sorted`

function, which correctly places the unsorted head element, and we end up with a sorted list.

RELATED TAGS

haskell

communitycreator

insertion

sort

CONTRIBUTOR

Abdul Monum

RELATED COURSES

View all Courses

Keep Exploring

Related Courses