The expressiveness of Haskell – Sorting.

What first excited me about Haskell was the expressiveness of the language. It somehow encapsulates thought and the problem being solved can often be seen clearly in the solution.
Take, for example, sorting a list containing elements of a general type ‘a’. For these to be placed in order it must be possible to compare them. So in Haskell the sort function can be defined as:

i.e. the sort function takes a list of ‘a’ and returns a list of ‘a’ and the restriction on the type of ‘a’ is that it must be an instance of the Ord class – this allows comparison of two ‘a’ s. The function can be implemented as

If you don’t know Haskell at all then just stare at it for a while and you may get an intuition of what’s happening!
Line 2 states that sorting an empty list just gives an empty list.
Otherwise, line 3, take the first item in the list and put it in a list [x]. Then prepend the recursively sorted list of all items that are less than or equal to x, i.e. sort left and append to [x] the recursively sorted list of all items that are greater than x, i.e. sort right. In these two lines:

left and right are known as list comprehensions. For example left means get all x’ from the list xs such that x’ <= x and similarly for right.

It might not be efficient but it is very, very pleasing.

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top