Recursion: An Indispensable Tool For Every Functional Programmer [Example With Insertion Sort]
Tags: fpseries, functionalprogrammin, haskell
Published: 2021-04-13 15:45:46

---
title: Recursion: An Indispensable Tool For Every Functional Programmer [Example With Insertion Sort]
published: true
date: 2021-04-13 15:35:21 UTC
tags: FPseries,FunctionalProgrammin,Haskell
canonical_url: https://thealmarty.com/2021/04/13/recursion-an-indispensable-tool-for-every-functional-programmer-example-with-insertion-sort/
---

This is the first of a series of articles that illustrates _functional programming_ (FP) concepts to imperative programmers. As you go through these articles with code examples in Haskell (one of the most popular FP languages), you gain the grounding for picking up any FP languages quickly. Why should you care about FP? See [this post](https://thealmarty.com/2021/04/13/recursion-an-indispensable-tool-for-every-functional-programmer-example-with-insertion-sort/).

One of the most important concepts is the use of _recursion_ in place of loops. Loops are an important tool for imperative programmer to perform repeated actions. Functional programmers use recursion (calling the function itself) instead. Below, I use the _insertion sort algorithm_ as an example. I first implement it in imperative style, then I implement it in functional style in Haskell.

## Insertion Sort

I’ve chosen insertion sort as an example algorithm to illustrate how loops and recursion serve similar purposes. Of course, many languages have a sorting algorithm built-in, so most of the time you don’t need to write your own.

The insertion sort algorithm can be described as: separate the given list of elements into two list: one sorted, one unsorted. The sorted list initially contains the first element of the given list while the unsorted list initially contains the rest of the elements. In each step, take the first element from the unsorted list, compare it with each element of the sorted list, starting from the right most (or left most) element. Insert the element right after the element it should follow.

### Imperative style implementation

Below is the pseudocode from [Wikipedia](https://en.wikipedia.org/wiki/Insertion_sort). See also the [C](https://gist.github.com/4401a113108da4d5cbfb8fbee800b63a), [C++](https://gist.github.com/thealmarty/f88189688e26db735a0aec83ad8e6ce3), and [OCaml](https://github.com/thealmarty/ocaml_algorithms/blob/master/sort/imperative_insertion_sort.ml) implementation. Don’t worry about understanding the code line by line, the main point is that we use two loops for the algorithm.

```
i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

```

You can see that `insertion_sort` is a function that takes an array `A` and sorts it **_in place_** , that is, it rearranges the elements in `A` as the function runs. When you run `insertion_sort` with array `A`, `A` becomes the sorted array, this is not the case in FP.

## Recursion

Instead of using loops for repeated actions, FPers use recursion. _A recursive function calls itself as part of its own function definition!_ It’s common to recurse on the _tail_ of a list. The tail is the whole list without the first element (the _head_). Like loops, recursion requires a terminating condition. Because the tail is guaranteed to have one fewer element than the original input, we know that as it recurses its input is smaller and thus it can terminate.

### Functional style implementation in Haskell

The Haskell implementation includes **recursive functions `sort` and `insert`** :

```
sort :: Ord a => [a] -> [a]
sort l = sortInto [] l -- initially all elements are unsorted
  where
    sortInto :: Ord a => [a] -> [a] -> [a]
    sortInto sorted [] = sorted
    sortInto sorted (l:ls) = sortInto (insert sorted l) ls

    insert :: Ord a => [a] -> a -> [a]
    insert [] elem = [elem]
    insert sorted@(s:ss) elem | elem > s = s : insert ss elem
                              | otherwise = elem : sorted

egL :: [Int]
egL = [23,2,5]
main = putStrLn $ show (sort egL) ++ show egL

```

The function `sort` is declared with its types first. `sort` is a function that concerns a type `a` that can be ordered (hence `Ord a` before `=>`). `sort` takes a list with elements of type `a` and returns a list with elements of type `a`. That is, instead of sorting the list in place, **`sort` returns a new list!** `sort` calls `sortInto` to perform the function of in the outer loop in the imperative implementation.

Inside `sort` we also define `insert`, which performs the function of the inner loop in the imperative implementation. But instead of calling each element by position like the `while` loop, `insert` is a function that takes two arguments, a sorted list, `sorted` and an element that is to be inserted in the correct position, `elem`. The function compares the element with the sorted list head, `s`, and the rest of the sorted list, `ss`, is passed to the recursive call to continue with the next comparison. The recursion terminates when either

- `elem` is not greater than the next element of the sorted list, and is inserted in front of that element. Or – `elem` is being inserted at the end of the list. The first pattern match case. The resulting list of this call contains the single element `elem`.

`sortInto` is also a recursive function defined inside `sort`. It takes as arguments a sorted list, and an unsorted list. Since `sorted` is a sorted list, we can put it in as an input to `insert` so that `insert` can insert the first element `l` of the unsorted list properly. `sortInto` then recursively calls itself to insert the rest of the elements of the unsorted list in to the sorted list returned by `insert`.

`sort` calls `sortInto` with an empty sorted list, and the whole unsorted list as the unsorted list.

Save the above code in a file named `main.hs`. After you install GHC, you can run it in a terminal:

```
> runhaskell main.hs
[2,5,23][23,2,5]
```

You can see that after running `sort egL`, `egL` stays unchanged. That is, FP preserves the inputs.

In this post, you’ve learned quite a few important concepts! We’re more aware of **types** , we learned that **a function takes an input and gives an output** (instead of performing actions _in place_), and we learned **recursion**. In the next post, I will show a glimpse of the power of FP with higher order functions, which gives the FPer tremendous expressive powers and enables many awesome and concise ways to describe algorithms. For example, **recursion schemes** , which let you describe recursion in a single line of code.

The post [Recursion: An Indispensable Tool For Every Functional Programmer [Example With Insertion Sort]](https://thealmarty.com/2021/04/13/recursion-an-indispensable-tool-for-every-functional-programmer-example-with-insertion-sort/) appeared first on [The Always Learning Marty](https://thealmarty.com).