The same criticism can apply to Java. But it's not a particularly good criticism. Unless you're interested in quantum physics, you really don't want to know what the machine is "really doing". You want to have useful abstractions that you can rely on.
The rabbit hole goes very deep indeed, and a lot of concepts that programmers treat as concrete are themselves abstractions that hide a lot of complexity.
The difference in level of abstraction between Java and Haskell is much smaller than the difference from either of them to what the actual machine is doing. In both cases you have a compiler, a language runtime, an OS & kernel, and processor microcode in between you and "the metal". Actually Java has one extra step, because javac emits bytecode that needs to run in the JVM, whereas ghc emits binaries that can be run directly by the operating system.
(Your comment about O(n^2) in time is beside the point -- quicksort is always worst case O(n^2), so it wouldn't be quicksort otherwise. All the implementations we're talking about have that same asymptotic behavior. The problem with the naive Haskell implementation isn't the big-O time, it's the big-O memory, which went from O(1) to more like O(n log n).)
listQsort :: Ord a => [a] -> [a] listQsort = V.toList . qsort . V.fromList
Also: > With Java, it's precisely visible what the machine is doing to execute your code. This is much less the case with Haskell.
This is very much a false statement. Java code runs through the JVM and its memory bloat, whereas haskell is compiled to native code along with its runtime. Both involve significant abstractions away from the actual machine instructions. It is more accurate to say that Java makes you think you can see what the machine is doing, but it is also far removed from machine code. One advantage is that with haskell, the compiler can reason about your side-effect-free code and optimize much more than java code.
The expectation is that pure functional languages gain a lot of benefits from (for instance) referential transparency which allow for optimizations which can not be provided by the compiler in languages which don't provide the same benefits to developers.
It's also true that this is potentially just theoretical. Sure, there's no way to ensure these optimizations exist given your compiler's implementation, but the article actually does mention that this has other issues and it's only for demonstrative purposes.
So, chances are it's a non-issue and if it is an issue then you still have the power to solve the problem later. No need for premature optimization, right?
Basically, bang out a slow but obviously correct implementation, and then iterate to convert it to be efficient, perhaps using things like 'equational reasoning'. However I haven't much experience with this technique yet...
I believe this is the technique used in Pearls of Functional Algorithm Design by Richard Bird (I have yet to read it)
You don't, because it's near impossible. In Haskell you have defined quicksort, not instructed your computer how to do it. That's the reason it's beautiful, but also the reason it's hard to iteratively refine your soluion. There is basically only one definition of quicksort: your program, and you can't iteratively "refine the definition"
You can try to make it in-place in Haskell but there is no clear transition from your initial version to the in-place version.
The in-place haskell one looks something like this (and that java code shows no sign of envy now). Answer: like this http://stackoverflow.com/questions/5268156/how-do-you-do-an-...
This is my main problem with functional programming: it makes it very easy to go 90% of the way in a very elegant matter. Once you hit that brick wall though, you come to a point where you'd cut an arm off for a mutable array.
Perhaps the solution isn't to write horrible Haskell but rather either use a less strict functional language OR outsource that 10% of the code to an imperative language, rather than making contrived, complicated code like the in-place Haskell quicksort?
This post explains what I'm talking about: http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird...
But I'll probably pick it up at some point in the near future.
The good:
1) The definition of the algorithm is clear. It shows "how quicksort works."
2) It's trivial to see (and prove) that the function will terminate, and almost as trivial to prove that it will result in a sorted list. So, it is easy to show correctness.
3) The polymorphism makes this an easily reusable function right out of the box.
The bad:
1) That implementation is very inefficient. At a glance I think it would be O(n^2) time. (Edit: this is misleading, because it's only O(n^2) in the same way that quicksort is always O(n^2). It is inefficient in terms of memory usage, though. And possibly other ways; for instance, I'm not sure how laziness would affect this. But I don't want to be spreading FUD...)
2) The "efficient" implementation given at the bottom is just as inscrutable as any other quicksort implementation I've seen. More so because of the monadic code, single-letter variables (pr?) and opaque library function calls (unsafePartition?) being made. And I'm not even sure that it would work on a list, although since V.Vector appears to be a type class, perhaps list is an instance of it.
3) Both the efficient and inefficient implementations are concise in large part because of their use of library functions. This is often a good thing: Haskell provides a great way to abstract things because of its parametric and ad-hoc polymorphism, and allows for a lot of reusable code. But it comes at a cost too, which is that the actual instructions you're giving to the machine are very far removed from what the computer is doing. Who knows how much code is actually executed, how deep the rabbit hole goes, to translate those beautiful 4 lines into actual machine instructions? With Java, it's precisely visible what the machine is doing to execute your code. This is much less the case with Haskell.
I suppose you could say (broadly) that functional languages excel at expressing what your program should do, while imperative languages excel at expressing how your program should do it. There are cases when you care more about the former, and cases when you care more about the latter. The reason I take issue with the quicksort example, is that list-sorting is a case where you definitely care more about the how than the what.
-------------------
EDIT, since two people called me out on it: It was an overstatement on my part to say that it's "precisely visible" what your Java code will translate to, but to suggest the two languages have the same degree of abstraction from the CPU is ridiculous. The code translation from Java to bytecode is quite straightforward, because most of the optimization occurs at runtime with JIT. There is a reasonably direct relationship between the code you write, the bytecode it gets translated into, and the instructions executed at runtime. At the end of the day, Java code consists of a series of instructions for the computer to follow, while on the other hand in Haskell, you aren't even technically giving instructions at all -- you're just writing equations. Compiled Haskell code is completely inscrutable.
Also, I should note that I am an enthusiastic Haskell hobbyist, and write it on almost a daily basis. Although I might not come across it here, I am a huge fan of the language; outside of the languages I use at work, by far the one I use most is haskell.