Monday, October 13, 2008

Sorting using Haskell

Last Friday night I had some fun writing sorts in Haskell. Yes thats right I spent my Friday night working on some rudimentary algorithms in an obscure computer language. Lets just say I'm in to that kinda thing. Oh well it beats being addicted to cough syrup.

So Haskell is fun. There I said it. It is the kinda language which lends much balance to ones style, is one is a imperitive/OO language flunky. The ideas in Haskell seem bizarre at first but become beautiful as they sink in. Sink they do, lets look at the first sort, the almighty BUBBLE SORT

-- Implementation of a bubble sort in Haskell
bubbleSort :: (Ord t) => [t] -> [t] -- signature
bubbleSort a = loop (length a) bubble a

bubble :: (Ord t) => [t] -> [t]
bubble (a:b:c) | a < b = a : bubble (b:c)
| otherwise = b : bubble (a:c)
bubble (a:[]) = [a]
bubble [] = []

loop :: (Num a, Ord a) => a -> (t -> t) -> t -> t
loop num f x | num > 0 = loop (num-1) f x'
| otherwise = x
where x' = f x

I imagine that looks weird. Well it should, if you are unaccustomed to Haskell. The syntax is much different than any OO language. I've had people tell me Python is too weird looking. Well this would just frighten those types of people silly. Lets talk about this code

The first thing to point out is the signature. In leyman's terms this says "take a list of something and return a list of something". The last [t] is going to be what is returned. The '(Ord t)' says that t must be of the typeclass 'Ord' as in 'Ordinality' which is related to being able to compare values. Don't worry too much about that for now, just know it allows us to do things like '>', '<', '==' and so on.

The rest is easy to explain. The bubbleSort function will loop x times, x being the length of the list to be sorted. For a list of 10 elements we loop 10 times. Each time we loop we call bubble. See the loop function takes a number (a) and a function (t -> t), and finally a value (t). What we end up doing here is calling loop again with the number decremented by one. We call bubble on the value, then passing the result right back into bubble IF the number is greater than 0.

This bubble function will go through the list comparing each pair elements, starting with the first and second, and swapping them if the first is greater than the second. This causes the largest value to 'bubble up' to the top of the list.


Pseudonym said...

bubbleSort a = iterate bubble a !! length a

Of course, a true bubble sort terminates when a bubble pass makes no swaps, just in case the list is "almost sorted".

robottaway said...

Thanks for pointing out that standard prelude function. I'm still pretty lousy at reusing the functionality already in there. Good point it should terminate, also should bubble one less per iteration, seeing how the top element is sorted.

Andrew Pritchard said...

bubble' (ll:[]) = [ll]
bubble' (l1:l2:ls) = (max l1 l2) : (bubble' ((min l1 l2):ls))

bubble x | x==res = res
| otherwise = bubble res
where res = bubble' x

-- that implements Pseudonym's version, I believe - it seems to work

robottaway said...

Works for me... but the returned list is in reverse order :)

if you switch min and max locations it will be in min to max / left to right order:

> (min l1 l2) : (bubble' ((max l1 l2):ls))

All around pretty clever and compact solution. Thank you!