News for hackers. Stuff that matters.
Re:Programming and thinking the functional way by thinkpad20 on Wednesday May 07, 2014 @01:45PM (#7711612)
Ah, the ole "quicksort in 3 lines" argument. There are a few things I take from this.

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.

Re:Programming and thinking the functional way by ef4 on Wednesday May 07, 2014 @02:48PM (#7711975)
> 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...

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

Re:Programming and thinking the functional way by xxs on Wednesday May 07, 2014 @03:10PM (#7712098)
quicksort is never O(1) memory but O(log N). On a flip note: Java's JITs are very mature to the point one may know what exactly the generated assembly would be (and display it as well -XX:+PrintAssembly)
Re:Programming and thinking the functional way by yanatan16 on Wednesday May 07, 2014 @02:15PM (#7711812)
Lists in haskell are lazy linked lists. Vector is a library that provides mutable allocated vectors a la Java's Vector. To use it with lists you would have to do (note the period is composition):

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.

Re:Programming and thinking the functional way by millstone on Wednesday May 07, 2014 @03:44PM (#7712267)
Your last line refutes your refutation! If Haskell really can "optimize much more," then it's harder to know from code inspection what the program will actually do at runtime. And if you don't know why your program is fast, then you can't know how to keep it fast. Does this seemingly innocuous change defeat an optimization? Hard to say.
Re:Programming and thinking the functional way by ww520 on Wednesday May 07, 2014 @02:09PM (#7711781)
The 3-liner qsort is kind of the marketing to lure in the newbies into the language. It becomes a problem when people start to believe the marketing as the real thing. People doing this kind of apple to orange comparison do a disservice to Haskell.
Re:Programming and thinking the functional way by monokrome on Wednesday May 07, 2014 @06:27PM (#7712989)
It's worth noting that the reason behind pure functional programming is that ideally lets you reason about your business concerns without needing to worry so much about these things.

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?

Re:Programming and thinking the functional way by Russell91 on Wednesday May 07, 2014 @03:01PM (#7712048)
Not sure how you find this as O(n^2). It's clearly the divide and conquer version with O(n lg n) expected time. The only asymptotic complexity issue of the algorithm is that it doesn't randomly pick p, so it will get O(n^2) perf on an already sorted list. It would be expected that you randomly shuffle a list before using this quicksort alg. When the author says this is not the true quicksort, he's referring to the fact that it needs O(n) auxiliary memory, because it's not swapping values in place (the real cost here is worse caching performance). It's definitely not an O(n^2) algorithm though.
Re:Programming and thinking the functional way by platz on Wednesday May 07, 2014 @02:29PM (#7711872)
from the "good", 1) and 2) can be helpful before you start working on an efficient implementation.

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)

Re:Programming and thinking the functional way by alkonaut on Wednesday May 07, 2014 @03:41PM (#7712252)
Question is: starting in the idiomatic Haskell implementation that you discover is too slow, what is the next step? How does one iteratively go from that to a slightly faster one, to an even faster one?

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?

Re:Programming and thinking the functional way by oakwhiz on Wednesday May 07, 2014 @04:42PM (#7712536)
The problem that you are describing occurs when you are trying to optimize a piece of idiomatic functional code that you have already written. Perhaps the solution could be to keep the code you have already written, and write a low-level, highly-optimized replacement alongside it, then have the compiler verify that the low-level code is provably identical in its output to the original function. If the code passes this test, then it is replaced with the optimized version. If you change either piece of code, and they do not match each other, then your code will not compile.
Re:Programming and thinking the functional way by platz on Wednesday May 07, 2014 @03:58PM (#7712314)
I mentioned Pearls of Functional Algorithm Design because it exactly describes how to do this. It may not lead to a solution in the ST monad, but it does tell you to to iterate to a better solution.

This post explains what I'm talking about: http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird...

Re:Programming and thinking the functional way by alkonaut on Wednesday May 07, 2014 @04:12PM (#7712379)
Sounds like a good read, sold!
Re:Programming and thinking the functional way by platz on Wednesday May 07, 2014 @04:19PM (#7712424)
I'm kind of on the fence about it - I've hesitated buying it because the post also explains that it's a notoriously difficult book - some of the results of the "swizzling" can lead to some inscrutable final programs.

But I'll probably pick it up at some point in the near future.

Re:Programming and thinking the functional way by louthy on Saturday May 10, 2014 @05:16PM (#7726879)
> it's a notoriously difficult book

Personally I don't find that to be true, it's perfectly logical mostly. It's definitely worth picking up imho.

Re:Programming and thinking the functional way by wting on Wednesday May 07, 2014 @02:35PM (#7711905)
A large reason why the naive, imperative quick sort performs well in practice is that it takes advantage of memory locality but the Haskell one doesn't.