My first attempt to write something in English (Don´t cut me some slack!)
Basically, the programs written in functional languages like Lisp or Haskell are based on function definitions. I don´t want, by no means, to give a thorough explanation of the features that functional languages offer because, among other things, I am not an expert on such languages (although I´d like to). I am writting this because not until I tried to implement some probs kinda recursive-natured, did I find how quick & fun this kind of programming style is.
Let´s set out to implement a naive algorithm for sorting lists in Haskell, so for a given input list, we get the corresponding sorted list. The function sort takes an argument of type list and returns a new list representing the former one in order.
-- Sort a list sort :: Ord a => [a] -> [a] sort [] = [] sort (x:xs) = insert x (sort xs)
The first line comprises the function definition, which takes a list of elements of type a, and returns the same type ([a] -> [a]). The string “Ord a” restricts the potential members of the list to types compliant with the ordering rules (integers for instance). But this is Haskell specifics, not very appealing. Let´s go to the implementation. The second line is the implementation of the function for an empty list, which in turn returns an empty list.
Lokking over the last line, we can notice that it defines how a non-empty list, (x:xs) being x the first element and xs the remainder, is going to be sorted. For that, it makes use of a new function named insert. Here you are:
-- Insert an element in to a list, maintaining the order
insert :: Ord a => a -> [a] -> [a]
insert y [] = y:[]
insert y (m:ms) | y <= m = y:(m:ms)
| y > m = m:(insert y ms)
This second function takes two arguments, the first one being an element of type a, and the other a list of elements of the same type. Same type restrictions as in the parent function. The return value is another list. The trivial case (insert y [] = y:[]) concatenates an element with an empty list. The general case says (last two lines): “if the element to insert is less or equal than the first element in the list, concatenate them. Otherwise, join the first element in the list with a recursive call using the same element and the remaining elements in the list”. Easy ha!
Let´s see the recursive call stack for this execution:
sort [9, 3, 5]
|
insert 9 (sort [3, 5])
|
insert 9 (insert 3 (sort [5]))
|
insert 9 (insert 3 (insert 5 (sort [])))
|
insert 9 (insert 3 (insert 5 []))
|
insert 9 (insert 3 5:[])
|
insert 9 (3:5)
|
3:(insert 9 5:[])
|
3:5(insert 9 [])
|
3:5:9:[]
|
[3, 5, 9]
Yay! Some may argue that this implementation is time-taking, that it does too many recursive calls even for small inputs. A complete resource waster. I couldn´t do anything else but agree with that, but, you know what? I don´t care! It´s just this code´s neatness what makes me feel thrilled. I look at it and I think: “Ey dude! It´s as pretty as a picture!”. If you still feel like sprucing it up, a good starting point could be this one.
Another good point in the functions above is that I didn´t say that the input list had to hold numeric elements! Surprisingly (not for an expert), the following execution outputs a nice result (guess why?):
sort ["Water", "The", "Dead", "In"] ... (call trace left out) ["Dead","In","The","Water"]
For the most part, this is what I wanted to show here. Isn´t it worth the hassle? At least for me, no doubts.
Posted by Rubén Barroso 
Century Minds 