Haskell, The beginning

Published on Tuesday, December 1, 2009

I started a course in Haskell, beginning to get to the end of the course and thought that I would add some small code-snippets here for guidance.

Insertion Sort

iSort :: [Int] -> [Int]
iSort [] = []
iSort (x:xs) = ins x (iSort xs)
                ins x [] = [x]
                ins x (y:ys)
                        | x <= y = x : (y : ys)
                        | otherwise = y : ins x ys

This will fit our needs, we could make it more compact like I will show you a bit later, but lets explore this example for a bit. We define the method iSort which takes one argument, the list we want to sort, and returns an array of integers that is sorted. We start by pattern matching the empty list and if the pattern match we return the empty list, this fit our needs and it's type correct, we have to have a base-case. Then we extract the first element of the list and store the rest of the list in xs. We want to insert the element 'x' at the correct place in the sorted list xs, to do this we insert it in iSort xs which is an sorted list as the calculations is performed bottom-up and not top-down. Inside the method iSort we define our own insert function called ins. This is a pretty ugly hack to prevent from having two separated methods but it works and performs the same as if we define it outside the iSort method. The ins method returns [x] if we only got an element and an empty list as input, otherwise it checks if the value of x is below or equal to y, in that case it adds x to the beginning of the array. If this is not the case it inserts x later in ys which is performed in the "otherwise" statement. Another way of defining the iSort method would be to define it like this.

iSort' :: [Int] -> [Int]
iSort' xs = foldr ins [] xs

However this example is a bit more complex than the previous one and it can be a bit tricky to understand if you havn't coded in haskel earlier. The thing that it does is that it takes the last element of xs and adds it to the empty list, then it takes the next last element and performs insert on the resulting list and so on until we have performed this on all elements of the list.


We can also define a very simple quicksort method, this is a real advantage of haskell!

qSort :: [Int] -> [Int]
qSort [] = []
qSort (x:xs) = qSort [ y | y<-xs, y < x] ++ [x] ++ qSort [ y | y<-xs, y >= x]

The example of qSort is also pretty easy to understand, just take an element x, part the array to two arrays, one array with elements less than x and one with elements equal to or greater than x and perform qSort on those arrays.

comments powered by Disqus