Hacker News Reader

That wiki link to an actual implementation of quicksort in Haskell is pure comedy gold (1):

"Unfortunately none of the above "real" quicksorts seems to compile as given"

"The program below is working very very slowly. It's probably slowsort."

"A more specific/direct translation (neither this nor the C version is polymorphic) is offered by Daniel Fischer, who reports that this version runs within 2x of the C version"

(and it's a completely unreadable mess that is clearly a line by line copy of the C code given)

What a complete and utter trainwreck.

[1]: http://www.haskell.org/haskellwiki/Introduction/Direct_Trans...

To be fair, QuickSort is particularly suitable for imperative languages that allow in-place modification of arrays. For functional languages, merge sort is a much more natural solution that is simple to implement, guaranteed to be efficient, and probably reasonably fast (though still unlikely to beat a QuickSort implementation in C).

To be fair, QuickSort is particularly suitable for actual computation hardware which has hardware features like numerically addressed, stateful random access memory. Imperative arrays happen to feature "in-place modification of arrays" not because it's a useful language feature but because it's a straightforward abstraction of the actual machine being programmed.

That distinction is really important, and something I think many language nerds completely fail to understand. Sure, often all that's "really" important is the abstraction of the "Human Design Space" idea being implemented, and that's a regime where high level language abstractions have lots of value.

But sometimes you want to actually direct the hardware. And there, as everywhere, it helps to use a language with the proper abstractions. C has them, Haskell doesn't. There's absolutely no shame in that!

But somehow people get fooled into thinking that somehow Haskell (or whatever language is involved in the argument, but it seems like Haskell people fall into this hole more than most) doesn't need those abstractions to be "as fast a C". And that's just insane.

To be fair to mergesort, it's particularly suitable for actual computation hardware too. It's mostly linear reads and writes, which almost all i/o systems heavily favor. GNU sort uses mergesort (in C).

GNU sort is designed to sort on disk though. If you actually watch it working on a giant file, you'll see it generating lots and lots of files in /tmp containing the merge lists.

This is because quicksort obviously requires fast random access to the whole arrays, and (at least when it was written) /usr/bin/sort would be expected to be able to quickly sort data that can't fit in memory.

So... if anything I think this is evidence to my point: in the performance regime, you have to match the algorithm choice to the hardware. Specifically here: sort is making up for the lack of memory by exploiting the comparatively (relative to virtual memory) fast streaming behavior of storage media.

Notably, stateful filesystem I/O is also an area where Haskell tends to fall down. I'm not at all sure a Haskell merge sort of the form used in GNU sort would do well at all, though I'm willing to be proven wrong.

> GNU sort is designed to sort on disk though. If you actually watch it working on a giant file, you'll see it generating lots and lots of files in /tmp containing the merge lists.

The number of files created is just an implementation detail; you could easily do everything in one file if you wanted to, or at most 2N files if you're not allowed to seek or overwrite files at all, and you want to do N-way merges.

Maybe GNU sort is just trying to avoid creating files larger than 2 GB (which is a problem on legacy file systems).

> Specifically here: sort is making up for the lack of memory by exploiting the comparatively (relative to virtual memory) fast streaming behavior of storage media.

Yes, also the fact that GNU sort can sort multi-terabyte files on 32-bit platforms, which otherwise wouldn't fit in memory. (Though systems with smaller process memory space than disk storage space are an oddity that will soon be outdated, I suppose.)

> I'm not at all sure a Haskell merge sort of the form used in GNU sort would do well at all

Well, even the on-disk sort starts by sorting chunks in-memory, which we have already established Haskell is bad at. However, the merge sorting part of the algorithm may well be I/O bound in practice, in which case Haskell should be able to do it just fine.

The only good reason I can think of why C could be faster, is that if you can merge more efficiently, you can choose a higher value of N for your N-way merge,

> stateful filesystem I/O is also an area where Haskell tends to fall down

What do you mean by this? AFAIK Haskell can read/write files just fine through the I/O monad.

> Notably, stateful filesystem I/O is also an area where Haskell tends to fall down.

Can you give an example? I do not understand what you mean. The filesystem is stateful, but I do not see that impeding Haskell.

> and it's a completely unreadable mess that is clearly a line by line copy of the C code given

I didn't find it unreadable, and I think the point was to copy the C implementation. I'm not sure what you were expecting.

In any case the unfortunate state of parts of the haskell wiki isn't a good reason to feel one way or the other about the language.

The haskell analogue to perlintro.html is http://www.haskell.org/tutorial/index.html

Some code to chew on, some features shown off: http://lambda-the-ultimate.org/node/2427

and a great writeup of what happens behind the curtain: http://research.microsoft.com/en-us/um/people/simonpj/papers...

Probably the reason Haskell's introduction has more explanation is because for most, functional programming language is unusual.

Evaluating a language by just reading the introduction is like reading the introduction of a book and saying that you didn't like it. Read it! :)

It seems we are focusing too much in a possible weak point and forgeting about several strong points Haskell has.

It is linked from the main page to answer the question "What is Haskell?" It is not supposed to an example driven page at all. The title of the wiki page could be changed to fix this though. The very next link is http://tryhaskell.org/ to learn Haskell in a example driven way.

I agree that I'm nitpicking a bit but I do think it's significant. It says something about the mentality of the community. First impressions matter.

But perhaps you could recommend me and others who'd like to try haskell a better introduction to the language? I'm still curious to try it.

I highly recommend (http://learnyouahaskell.com/)

Yes! That's a great introduction, but you must have a sense of humor. I love that book.

Curious to know what you think of http://ocaml.org, specifically the code example on the front page and the further examples it links to (http://ocaml.org/taste.html)

Looks like what I would expect from a language introduction. Explains the syntax, shows off some features, gives you snippets of code and tells you how to feed them into a REPL. It's a good way to start and get people interested in the language I think.

Funny, I've never seen that page, I always land on Inria's page(http://caml.inria.fr/).

Me too. Quite delighted to see ocaml having a refreshed page and active community.

Plus quicksort is a classic morass- by the time you harden it enough to deal with real world data you could have written a proper merge sort with similar average case performance and much better worst case guarantee. My rant on quicksort: http://www.win-vector.com/blog/2008/04/sorting-in-anger/

Interesting read, thanks for linking it. When I need to write a sorting algorithm, I usually for Merge Sort, because I can never remember the exact details of swapping/partitioning of QuickSort. It seems much more natural to say "split your data in two, sort them, merge them together". And when I'm feeling damn fancy, I use an InsertSort when the size of the dataset is less than 7-8, another algorithm that I find difficult to forget (at least, the recursive definition; I usually need some paper and pencil to do the in-place version).

That is not the best introduction to the programming language by means of practical examples, but it does not look like it is supposed to be either. At least from Haskell.org it links from "What is Haskell?" Which is a very different question then what can I do with Haskell.

> After a couple of paragraphs brainwashing you about how good functional programming is, you finally get to some code.

Whenever I see a page about a new programming language I usually skip all the marketing speech at first and look for a code fragment to examine first. After that I'll start reading the actual text.

"They also give a link to a more direct (and faster) C-to-haskell version of the quicksort[1]. Hey, it's actually longer than the C version! And it uses 3 imports. And it's still slower than the original C. Oops" that made me laugh a few years (?) ago and it still does :)

Is there any language intro page that shows a good sized working program?

Yes. Racket has a great intro-page and download links etc. No BS.

http://racket-lang.org/

the question was "a good sized working program", the racket page is a great page but only has a few haikus, so "no" should be your first word, even if the rest of the comment is correct :)