A small blurb about Insert Sort in Haskell (and Python)

InsertSort.md

This is completely inspired by the paper linked here: http://www.cs.ox.ac.uk/people/daniel.james/sorting/sorting.pdf

In brief

Insert Sort is a method of sorting in which you "reinsert" each element into the list of elements before it. Essentially, for each element, you move that element left past each element that is bigger than it.

The algorithmic invariant you have is that the list up to the current element is sorted.

Python

In python, you might implement it like this (from wikipedia):

def insert_sort(s):
    for i in range(1, len(s)):
        val = s[i]
        j = i - 1
        while j >= 0 and s[j] > val:
            s[j+1] = s[j]
            j = j - 1
        s[j+1] = val

Note that for each element, val, the function places val into its sorted location into the list below it. Thus, before inserting val, all elements to its left are sorted. After inserting val, since val was placed in sorted order, the list including val is sorted. A new val is selected (the next element in the list).

Essentially, each val is being inserted into the list on its left.

Simple stuff.

Let's talk about Haskell.

For the next part, there are a few Haskell built-in functions worth discussing. First, any Haskell function is curried automatically. That means that if a function f takes 2 arguments, f first_arg is a function that takes 1 argument.

foldr is a function much like reduce in python. Here is its type signature:

foldr :: (a -> b -> b) -> b -> [a] -> b

Its first argument is a function (this is the (a -> b -> b) part) that takes 2 arguments (one a and one b -- they could be different types) and returns a b (its return value is what the last arrow points to). Its second argument is a b -- in this case, it is a starting value, or default value (in the case that its next argument is an empty list) Its third argument is a list of as.

Thus, foldr f b as calls f on each element of as. It could be defined like this:

foldr _ b [] = b
foldr f b (a:as) = a `f` foldr f b as

That is, you apply f to a and the result of the recursive call to foldr. A fairly trivial usecase for foldr is summing a list: foldr (+) 0 [1..5] Note that the technical way these numbers are added (relevant if f is not associative) is: 1 + (2 + (3 + (4 + 5)))

Finally, this lets us discuss a Haskell implementation of Insert Sort: Define the following insert method:

insert::Integer -> [Integer] -> [Integer]
insert y ys = xs ++ [y] ++ zs
    where (xs, zs) = partition (<y) ys

Then insert sort can be defined with the following one liner:

insertSort :: [Integer] -> [Integer]
insertSort = foldr insert [ ]

Note that insertSort is a curried function... just foldr with function insert and default value of an empty list.

Neat, huh?