Functional Style Selection Sort in OCaml

In this post I talk about what I have tried and learnt in the process of writing the functional correspondence of the imperative selection sort I wrote earlier in OCaml.  I learnt a lot in this practice because functional selection sort is not straight forward!

The First Attempt

At the beginning, I thought functional selection sort would be easy!  After all, it’s just another sort algorithm and I feel I’ve manipulated lists with recursive functions pretty well.

So, I wrote select pretty quickly.  select takes a list and an element and returns either the list (if the element is smaller or equal to the smallest element of the list) or the list with its smallest element taken out and the given element added to it.  You would notice it seems complicated – yes, the first lesson I learnt was to keep your functions as simple as possible!

There are two more problems with selection sort that I did not solved.  First, functions typically return one result.  For selection sort, you need two results: (1) the minimum element of the given list and (2) the remaining list which is the given list with the minimum element taken away.  select returns the remaining list after the smallest element was taken out.  However, I was having trouble taking out the other result of select, which tells me the smallest element in that list.

Second, selection sort requires putting the minimum element of the list at the beginning of the list.  Recursive functions typically cons (::) or append (@) the results of the function at the end.  It’s obvious that I need another function that cons the minimum element in each recursion.

Solutions I tried

1. Returning a tuple: it is possible to have a function that returns a tuple with two types, and then use pattern matching to extract the result.  That is, select can return the minimum element of the list and the remaining list.  It seems awkward and more complicated than is needed though.
2. Higher order functions: since I know that I need to cons the minimum element in each recursion, I can put select in another function to process it.  Note that the code on github using this approach does not work yet – I could probably debug it and make it work but it seems more complicated than is needed and so I tried another approach.
3. Put the two results in one such that they can be extracted:  This is the first version that works.  It was straight forward enough to write and make it work.  It includes two functions I wrote, but I also used the built in List module functions (to extract the results), and it does not follow the selection sort as closely.  So I also worked on an improved version.
4. Write multiple straight forward functions and a function to manipulate them to execute the algorithm:  I am happy with this second version because it does not require any built in functions, and follows the algorithm closely.  It took me a very short time to write, although it has three functions in it!  But each of the functions are very short and easy to read.  Each of them gives one result so there is no need to extract the results!

Things I Learnt

I tried many different solutions on top of the highlighted ones above, and I learnt a lot!  The most important things are:

• You should make functions as stand alone as possible for clarity and debugging.  Avoid putting functions in functions whenever possible.
• The type signatures OCaml returns are useful for debugging.  Annotating your code also helps.
• Make sure you load your code properly.  Test that you have done so before debugging.
• Simplify your functions as much as you can.
  • When you type up your comments that explains what your function does, it should not be difficult to describe.
  • Your functions should take as few arguments as possible.
• Don’t be afraid to write many functions!  As long as you keep the functions simple, each doing one job and returning one result, it actually makes your code shorter and easier to read!

Functional versus Imperative

After this exercise, I see some advantages of functional programming over imperative.

First, because functions separate each job and results nicely, for more complicated processes, it is likely less confusing than imperative style programming.  I was amazed how easy and fast it was to write selection sort after I take the approach of writing many simple functions!  There may be some trick for doing the same for imperative style (please feel free to comment and let me know!).  However, I haven’t found how you can avoid more complicated codes like nested loops etc in imperative style.

Second, I had to do a lot of testing and debugging in this practice and I appreciate that functional style programming does not change the content of the argument.  So, when I define a list and sort it, it returns another list without changing the content of the list I defined.  Of course, if you want the result named, it’s easy to do so.  This is more flexible than imperative programming, in which you alter the original list.

I’m still having so much fun!  Look forward to learning and writing merge sort!