Comment by tome

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