I am a fan of functional programming. I find that paradigm extremely elegant and expressive. I used Scheme when I started university and I was happy. I discovered the Haskell programming language some years ago and it was love at first sight.

According to the official Haskell site,

“Haskell is a general purpose, purely functional programming language featuring static typing, higher order functions, polymorphism, type classes and monadic effects.”

This is a mouthful but is actually a good description of the language. One essential feature of Haskell is its typing system: Haskell features static typing but types are never specified explicitly but are always inferred by the compiler!

Another “feature” is the absence of variables. Yes, you don’t have any variables (i.e. something that can change its value) in Haskell. And if you think about it it’s also the case in SQL, Prolog, XSLT, etc.

Hugs 98 is a nice and easy Haskell programming environment ideal for beginners. GHC is a state-of-the-art Haskell compiler which regularly produces executables that run faster than programs written in C! Both are multi-platform and open source.

Ok. I hope you are salivating. And, cerise sur le gateau, the Haskell syntax is beautiful.

Here is our old friend Quicksort:

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

Quicksorting an empty list gives an empty list. Quicksorting a non-empty list (which can always be written as an element x followed by a list of xs (get it?)) is the Quicksort of all elements from xs which are less than x (the pivot) followed by x followed by the Quicksort of all elements from xs which are greater or equal to x. Beautiful isn’t it? In case you don’t think this can be an actual program, you are not alone (read part 7 Lessons learned)

A more involved example is this program I wrote some years ago:

data Tree = Empty | CreateTree Integer Tree Tree

flattenInfix Empty = []
flattenInfix (CreateTree v l r) = flattenInfix(l) ++ [v] ++ flattenInfix(r)

flattenPrefix Empty = []
flattenPrefix (CreateTree v l r) = [v] ++ flattenPrefix(l) ++ flattenPrefix(r)

flattenPostfix Empty = []
flattenPostfix (CreateTree v l r) = flattenPostfix(l) ++ flattenPostfix(r) ++ [v]

insert x Empty = (CreateTree x Empty Empty)
insert x (CreateTree v l r) =
    if x<v then CreateTree v (insert x l) r
    else CreateTree v l (insert x r)

putLeft Empty Empty = Empty
putLeft Empty a = a
putLeft a Empty = a
putLeft a (CreateTree e l r) = (CreateTree e (putLeft a l) r)

remove x Empty = Empty
remove x (CreateTree e l r) =
    if x==e then putLeft l r
    else if x<e then (CreateTree e (remove x l) r)
    else (CreateTree e l (remove x r))

which implements a binary search tree with a number of common operations (three kinds of flatten, insert and remove). Read the code. I’m sure most of you will understand it much more than the equivalent C or C++ program…

The binary tree can be used like this:

tree = (CreateTree 20
    (CreateTree 10
        (CreateTree 5
            (CreateTree 1 Empty Empty)
            (CreateTree 7 Empty Empty))
        (CreateTree 15 Empty Empty))
    (CreateTree 30
        (CreateTree 25 Empty Empty)
        (CreateTree 35 Empty Empty)))

> flattenInfix tree
[1,5,7,10,15,20,25,30,35]

> flattenInfix (insert 4 tree)
[1,4,5,7,10,15,20,25,30,35]

> flattenInfix (remove 30 (insert 4 tree))
[1,4,5,7,10,15,20,25,35]

> flattenInfix
*** Expression : flattenInfix
*** Of type : Tree -> [Integer]

Do you see that Haskell has inferred that flattenInfix is a function which takes a Tree and returns a list of Integers! Can you see why?

Welcome to the world of Haskell!