Comment by chuckadams

14 days ago

> My favorite example of this is implementing quicksort. It's significantly easier in C than it is in Haskell.

Oh please, what's so hard about

    qsort :: Ord a => [a] -> [a]
    qsort []     = []
    qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
        where
            lesser  = filter (< p) xs
            greater = filter (>= p) xs

folks, take that with a big ol /s, you would never want to actually use that algorithm. But the real deal isn't all that awful: https://mmhaskell.com/blog/2019/5/13/quicksort-with-haskell

6 comments

chuckadams

trealira 14 days ago

I know you're being sarcastic, but even in this linked-list quicksort, it could be made more efficient. By defining lesser and greater separately, you're traversing the list twice. You could compute them at the same time by changing those last two lines to this:

  where
    (lesser, greater) = partition (< p) xs

I just learned about the existence of this function today, and wonder why I had never seen it used before.

https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-...

chuckadams 14 days ago

Heh, I've used some version of partition in my TS/JS code ever since underscore.js. But "Haskell Quicksort" is basically a code meme now, and I didn't think to optimize it (though I think the original was a one-liner using list comprehensions)

hnfong 14 days ago

Arguably the issue with "quicksort in Haskell" is not that it's "hard" to implement, but rather it defeats the whole purpose of using a "purely functional" language.

The pragmatic way to look at Haskell is not that it's purely functional, but rather, you could write <del>imperative code</del> Monads if you wanted, and that gives a "functional by default" environment, whereas most imperative languages default to mutable objects etc that are not friendly to functional-style programming.

But then the more modern languages are catching on with immutable by default variables etc. so in the end the differences between newer languages may not be that great after all...

simiones 14 days ago

Well, I'd say using an entirely different collection type than the rest of language (STArray instead of [a]) is already a big complication. It also ends up being more than double the size of the Java code. And, as the author admits, it's actually even slower than the original not-quicksort implementation above, because it actually has to make a copy of the original list, and then return a copy of the mutated array.

So, one of the best sorting algorithms ever devised is not actually usable to sort a [a] in Haskell... I maintain this is a good example of making an easy problem tough.

tome 14 days ago

> I'd say using an entirely different collection type than the rest of language (STArray instead of [a]) is already a big complication
Haskell uses many different collection types, just like any other language. Why not?
> it's actually even slower than the original not-quicksort implementation above, because it actually has to make a copy of the original list, and then return a copy of the mutated array.
Sure, but it could also not do that, if callers are happy to provide a mutable array, just like any other language ...
> one of the best sorting algorithms ever devised is not actually usable to sort a [a] in Haskell
Indeed! One of the best algorithms for sorting a mutable array can't be used on an immutable data type, just like any other language ...
None of this invalidates your original claim that "It's significantly easier in C than it is in Haskell" of course.
chuckadams 14 days ago

quicksort2 has a very reasonable constraint of Array, it's the helpers that use the STArray implementation. I suspect it wouldn't be hard to port to MArray, though I don't know that it would perform any better (maybe avoiding some copies since MArray is actually usable outside of runST). I also suspect the overhead of the copies pays off with larger lists given the lack of space leaks compared to the naive algorithm. Some benchmarks of different-sized lists would have been nice.
I'm not a cheerleader for Haskell, it's not the most appropriate language for every job (certainly not for quicksort). But some folks suddenly become hyper-optimizing assembly programmers whenever anyone has the thought of porting a sql crud app to another language... Horses for courses and all that.