Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quicksort is the new Hello World

blog.rmontanaro.com

Post reply on HN
Print view View original

11–20 of 64 posts

Re: Quicksort is the new Hello World

#11

Post by Nitramp »

dzorz wrote: post #6

Although this version is very simple, concatenating and creating lists at runtime ruins performance (and it takes extra memory). Please make it a good example by doing a version of Quicksort with in-place partition.

That's actually a nice nab for functional programmers. They run around all the time telling how nice their language of choice is, showing off quicksort in three lines of code.

But please don't have the audacity of pointing out that original quicksort was supposed to be an efficient in place sort, not a mental exercise in beauty of a language. Then you get a Haskell version that is in place, and supposedly fast. It's about 10 lines longer than the C version, uses Monads, ST, recursion, "unsafeRead/Write", "rscan", "lscan", "swap", "sloop", etc., all together about 20 concepts, built-in functions, etc.

Also, of course, if it really should be fast, you have to use several compiler hints and macros to make it type specialize and all. Obviously.

The C version is shorter, uses nothing but array accesses, do/while, if, int comparisons, and recursion. If you want to explain the C version to a novice programmer, it will maybe take you half a day. The inplace Haskell version? Uhhh, yeah.

I can't help it, but things like these leave me with the impression of Haskell being a theoretically really nice language whose utility in actually getting things done seems somewhat questionable.

Re: Quicksort is the new Hello World

#13

Post by pmjordan »

l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

In fairness, in-place sorting usually isn't what you want in functional programming. Immutable data structures help enforce the pure functional constraints. Of course, in practice, your library code will probably make a mutable copy, sort that in-place and then return an immutable copy/representation of the result, which is hopefully more efficient. (Disclaimer: I'm no Haskell programmer; my FP experience is limited to Lisp dialects)

EDIT: As a curious example, Clojure's sort function actually converts the sequence to a (Java) Array and calls java.util.Arrays.sort() on it, then turns it back into a sequence:

https://github.com/clojure/clojure/blob/b578c69d7480f621841e...

Re: Quicksort is the new Hello World

#14

Post by brazzy »

l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

Indeed. It's amazing just how difficult it is to write a correct in-place quicksort that handles all edge cases. It won't be short and elegant either. Just go ahead and try it.

Re: Quicksort is the new Hello World

#15

Post by Deestan »

sb wrote: post #10

tl; dr, but a quick note: the presented algorithm takes the first element as the pivot element p: qsort (p:xs) = ... This is not recommended as it results in worst-case behavior on sorted input lists. (Another commentor correctly pointed out that it requires extra memory for the intermediate lists, too.)

It is just a toy implementation. If we're going to worry about practicals, then it's not recommended to use your own general purpose sorting implementations at all. For general purpose sorting, the standard library "always" has the best implementation.

Re: Quicksort is the new Hello World

#16

Post by xentronium »

brazzy wrote: post #14
l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

Indeed. It's amazing just how difficult it is to write a correct in-place quicksort that handles all edge cases. It won't be short and elegant either. Just go ahead and try it.

http://pastie.org/1367726 -- it's not that hard, really :)

* especially with naive pivot from the middle of array

Re: Quicksort is the new Hello World

#17

Post by lelele »

l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

> Thus, even if the sample code is simple and elegant, a real-world implementation would surely be a bit longer than the given example.

Nice thought. What's the purpose of showing code which you won't be using in a real-world application? Making you think the language is more expressive than what it really is?

Many people say Haskell code is elegant and concise. Would this be the case if code we were shown would be real-world Haskell?

Re: Quicksort is the new Hello World

#19

Post by yoyar »

Hello World is there to validate that you can setup, compile and run a program in your new language of choice. Complicating that process by trying to write something non-trivial defeats the purpose of the exercise. I call BS on this article.

Re: Quicksort is the new Hello World

#20

Post by mwill »

I still write and run Hello World in languages I am well versed in when I start working in a new environment, purely as a sanity check. In many cases it is the simplest starting point to ensure you have a working environment.

As far as familiarizing myself with a new language, I usually write a Hello World, then add some variables, and some functions or whatever is relevant, and just focus on the syntax of the language, or in the case of a platform or framework, take a look at building trivial components.

Not a language, but a platform example: I recently explored ExpressJS (If you're not familiar, its a framework for node.js web apps.) and my workflow was: Make a hello world server, Add a few routes and a static handler, Add some views, Add some middleware, Build it into a basic blog. (Because it's always a blog first, right?)

The whole process was quite quick and gave me a very strong jumping point for ExpressJS. Implementing quicksort or something similar as my first crack would probably have been pretty useless. So for me its all about context; I tend to start at Hello World and quickly grow something simple, but relevant to the language or platform.

Post reply on HN