Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Journal of Dom2 (2981)

Tuesday March 23, 2004
02:45 PM


[ #18029 ]

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 ),
        qsort( grep { $_ > $x } @xs ),

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.
  • 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.

    • 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.


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

        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:

  • 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
    • 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.