The parent poster is not lamenting that Haskell lacks a trivial sorting function.
They are lamenting that implementing a trivial sorting function in Haskell is difficult.
They are lamenting that implementing a trivial sorting function in Haskell is difficult.
Quicksort isn't really hard, you just do it in IO and it looks about like what you'd see in any imperative language. (or you can use ST, but then you have to know about ST).
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
biggerSorted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSortedIt is only linear when you force it to evaluate, which ideally happens only once (amortized) in your program when the result is consumed. As long as you are careful, you don't get the bad quadratic performance that you'd get from something like eagerly appending a character to a string in a loop in Java. There are either gotchas, though, including relying on the compiler to do things in constant space that naively look linear, and also knowing when the compiler won't help you and you have to structure your computation manually.
My biggest problem with Haskell is how GC and lazy-evaluation makes it very difficult to reason about what the hardware is actually doing at a given point. I know there ways to inspect and control it, but I've found myself preferring languages that have simpler mental models.
edit: also, how is the pivot element selected there?
Obviously picking first element as pivot makes for a very poor Quicksort. Though I presume a better approach, say median of first, mid and last elements, would add but an extra line?