Haskell

Dom2 on 2004-03-23T19:45:05

As a fine example of the kind of Yak Shaving that I tend to indulge in, I've studied a lot of Haskell over the last few days. It's a really rather pleasant functional language. I picked up a book for it a while ago, the first time I thought about looking at Relax NG, when I noticed that James Clark had written examples of the validation algorithm in it.

So naturally, the book has sat on my shelves for the best part of a year with a bookmark about 1.5 chapters in.

It's only now in the last week or so that I've made a concerted effort to pick it up again and go through it. I'm nearly halfway through and enjoying it thoroughly. I've always enjoyed programming in the functional style, even in Perl, but Haskell feels so much nicer (within its realm).

What really caught my eye, though, was the definition of quicksort. I've read descriptions of the algorithm a few times (I'm not a trained Computer Scientist and have no formal training), but never really understood it. The implementation in the book just blew me away with its simplicity:

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

It's not the fastest implementation, it's not the most general. But I find it an incredibly clear demonstration of the algorithm. This is my rough translation in Perl.

sub qSort {
    return unless @_;
    my ($x, @xs) = @_;
    return (
        qsort( grep { $_ <= $x } @xs ),
        $x,
        qsort( grep { $_ > $x } @xs ),
    );
}

---

slow

mary.poppins on 2004-03-23T22:07:59

Is there a fast native compiler for Haskell? The
numbers I saw (from the shootout) made Haskell
look so much slower than ocaml that I really
didn't see the point.

Re:slow

Dom2 on 2004-03-24T00:02:54

I've only really played with hugs, so I'm not totally sure. You might wish to have a look at the implementations page.

I've not played with OCaml at all, I just liked what I saw in Haskell.

-Dom

Re:slow

mary.poppins on 2004-03-24T00:13:27

ocaml rocks, but the standard library kind of
sucks, and the compiler is QPL-ed, which totally
sucks.

Also, dynamic linking is kind of half-assed, and
isn't even implemented unless you're running Red
Hat / Debian / etc..

A good ocaml intro is Rich Jones's tutorial:

    http://www.merjis.com/richj/computers/ocaml/tutorial/

Optimized for what?

educated_foo on 2004-03-24T01:15:01

I have also enjoyed playing around with Haskell, but it ends up striking me as the apogee of languages optimized to solve the classic conference-paper problems: factorial, fibonacci, and quicksort. As a result, these algorithms look beautiful in Haskell, but things quickly get hairy when you venture off the path. For example, let's say you want to be able to pass your program a flag to print out the pivots your quicksort uses, to see if it's hitting the O(n^2) case or whatever. You suddenly find yourself either having to change it to return a list of pivots, or getting caught in the tar-baby that is the IO monad. And you can get a similarly elegant quicksort without Haskell's painful purity by just having list comprehensions in your language (e.g. Python).

Re:Optimized for what?

Dom2 on 2004-03-24T07:33:21

I agree with you; it does seem to be optimised to be a teaching language. I don't find anything particularly wrong with that, so long as the aims are clearly stated. It's certainly worked in my case. :-)

Off the top of my head, I can only think of one application in Haskell: darcs. Mind you, I can only think of one in ocaml: MLDonkey. I'm sure there are more, but I don't think that there are that many...

I wish I knew what my point here was, but I've just woken up. Darn.

-Dom