I like Haskell a lot…

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!

Comments

  1. Haskell is all over programming.reddit.com, and I can understand why that is so. The idea of programs that access data only in read-only mode is attractive: multi-threading is vastly simplified without the risk of blocking calls.

    But I still can’t get my head around Haskell! And, I’m particularly good at learning new languages. Maybe, the concepts of object-oriented programming are just too ingrained in me :-)

  2. Functional programming has a big future for the reason you mention: referential transparency.

    Google and the parallel processing people are already using FP concepts. And the future of concurrent programming might be Data Parallel Haskell

  3. hmm.. you seem to be someone who falls in love at first sight a lot!
    ruby, now haskell :p

    Another “feature” is the absence of variables. Yes, you don’t have any variables (i.e. something that can change its value)

    hmm.. i would feel out of this world without variables.
    Anywayz, i guess i’ll have to touch some haskell also for my eoy project

  4. Hi Selven,

    I only write about things I like, that’s why you feel that I regularly fall in love with new things.

    Incidentally, here are some languages I like a lot: C, Scheme, Java, Ruby, Smalltalk, Haskell, SQL and AWK.

    As for the lack of variables, have a look at declarative programming

  5. Cubicle Prisoner says:

    What an elegant quicksort example. And completely pointless, of course, because quicksort relies on direct indexing/updating in place to be quick, which you don’t get in Haskell.

  6. The Glasgow Haskell Compiler is actually very good and the code it produces is more efficient that the latest Java 6 JIT compiler…

    I guess that’s good enough for me… especially from my pedagogical perspective.

  7. One of the courses in the CS program of my university uses the Clean programming language. I don’t really know any Haskell, but Clean is supposed to be very much like it. I think some of the differences are how they handle I/O (Haskell uses monads, while in Clean you can also choose to use the uniqueness type), performance (Clean is very fast) and cross platform support (Clean is primarily developed for Windows). Aside from that there are some small syntactic differences.

    I quite liked Clean during the initial stage of the course, where the problems we had to solve were small. In the final project however, we had to use this large framework the teachers made for us, and I started to have a lot more trouble. I don’t know how this is in Haskell, but Clean’s error messages aren’t exactly clear. Also, I really missed using variables and side-effects when debugging (you can’t just put a ‘print’ statement somewhere). I hope someday I will learn to effectively work with these features/deficiencies.

    It is unfortunate that Clean is so rarely used. However, I will try to learn Haskell too, because I think that it will probably be around for longer and be more actively developed and supported.

  8. I’ve heard a lot of positive opinions on Clean. I should give it a look.

    Haskell is great also. Hugs is a very good environment to learn Haskell. And GHC rocks. I am especially looking forward to the concurrent extensions to GHC, specifically the Data Parallel part being worked on by Simon Peyton-Jones.

  9. @Cubicle Prisoner

    When you are using immutable data structures in-place updates and direct indexing can be done under the covers. That you can’t do these things directly in Haskell doesn’t mean the compiler is equally incapable.

  10. Cubicle Prisoner: You’re more or less right. Haskell’s basic list type is a linked list; mergesort is more appropriate for those.

    But then, who cares about sorting algorithms? Just use List.sort, and leave it to the library writers. (GHC’s library uses a mergesort, in case you’re wondering.) Or put your data in a Map or Set, and use toAscList to list the elements in order.

    Jordi: If you use GHC (not sure about other Haskell implementations) you can use Debug.Trace.trace to print a message when an expression is evaluated. I’ve seen it described as “a refreshing desert in the oasis of referential transparency”. But the main debugging method I use is to take expressions apart until I can see the error. Referential transparency really helps there.

  11. Catalina says:

    Can you tell me more about the putLeft function you wrote?…What does it do?

  12. Hi Catalina,

    putLeft is a helper function for remove.

    putLeft takes two trees as parameters (the first tree has values which are ALL strictly less than those in the second tree) and creates a new tree which is a binary search tree.

    To do that, all the nodes from the first tree are inserted into the second tree as left and as down as possible.

Speak Your Mind

*