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:
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])
find_min() function returns the minimum element in the list.
find_min :: [Int] -> Int, shows that our function takes a list of integers and returns an integer.
x:xsin 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.
remove_one function finds a particular element in a list, removes it, and returns the remaining 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
Let’s put all the pieces together.
find_minfunction 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
View all Courses