On Tue, Jun 22, 2010 at 4:18 PM, Andrew Coppin <andrewcoppin@btinternet.com> wrote:

What the...?

Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-)

Even so, it's not nearly as elegant to behold as, say, the quicksort algorithm, despite being of roughly similar complexity. Still, it's shorter than what I had.

I would argue that quicksort is considerably simpler, as it doesn't have to maintain an explicit tree, lookup and merge values, deal with bits, etc.

For something, perhaps closer in spirit to quicksort, and still compression-oriented, I have an implementation of LZ78 for decompressing streams directly into a monoid, rather than reconstituting the result, which also winds up remarkably terse and a great deal more general than its imperative counter-parts. ;)

http://hackage.haskell.org/packages/archive/monoids/0.1.36/doc/html/src/Data-Generator-Compressive-LZ78.html

-Edward Kmett