In tests and homework, we would implement the one-liner quicksort with paper and pencil, much like a math test. In a pencil implementation of that Haskell, it is n log(n). Each line on the paper represented one level of recursion.
Implementing it on silicon requires the trade-offs you mention. But silicon is just an implementation left to the reader...
EDIT: I guess where I'm coming from, Haskell was used in the context of the Theory of Computation, not real-world implementation details and the like.
