12 ms·

The one that blew my mind when I was in college was a simplified version of quicksort in Haskell. It's just so elegant and clean. quicksort :: Ord a => [a]

by switz 7y ago

The one that blew my mind when I was in college was a simplified version of quicksort in Haskell. It's just so elegant and clean. quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter (< p) xs greater = filter (>= p) xs Now surely someone may come along and point out how this isn't a true quicksort[0] because it doesn't partition the elements in place, but it's more of the simplicity of the logic and its readability that showed me how beautiful functional code can be. [0] https://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort https://stackoverflow.com/questions/7717691/why-is-the-minim...

ridiculous_fish 7y ago
Unfortunately it's also incorrect! It discards NaNs, as they are neither < nor >=.
- fulafel 7y ago
  I would argue that this is better than most alternatives.
- maweki 7y ago
  In the example there was no talking about floating point numbers. The ordered type _has_ a total ordering as shown by the Ord typeclass restriction.
hyperpallium 7y ago
I saw a similar version in erlang (in Joe Armstrong's Programming Erlang) and agree it beautifully illustrates the concept of quicksort. Apparently, Tony Hoare came up with it when he took a class teaching him recursion (i.e. he was a student). But the flaw you note unfortunately undermines performance... the "quick" in "quicksort". Thus, IMHO it's a compelling illustration of the profound strengths and weaknesses of fp.
0b01 7y ago
This may be an elegant piece of code at first glance except the niceties of quicksort such as cache locality and stability come entirely from the in-placeness of the partition procedure.
fdsdsa_7777 7y ago
I won't comment on how quicksort-y this is, but the combination of pattern matching and recursion is bread-and-butter Haskell. A number of seemingly complex algorithms can be implemented in a similar way. Having said that, it is elegant and clean and -- taken by itself -- does make Haskell very attractive.
xwowsersx 7y ago
Agreed that this is beautiful purely from the standpoint of how there is essentially no disconnect between the concept of the algorithm and the way it's expressed in code. It's almost the math/algo just translated directly into code (not commenting on the efficiency or other issues that may exist).
nwallin 7y ago
Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of quick sort, it's straight up bad. This implementation of quicksort is actually a great example of why functional programming sucks. It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption. So a normal programmer might sort via quicksort in Haskell because it's the optimal sort in imperative languages even though naive Haskell quicksort is objectively worse in every way than naive Haskell mergesort. Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++. And that's a very low bar.
- kccqzy 7y ago
  > It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n) space. Use of randomization would result in a high probability of choosing a good pivot element, but even then you can expect approximately O(log n) space. Also would like to see why you think the Haskell version has enormous constant time overhead. Where do you think this overhead comes from? If you are comparing to an equivalent program in C++ then sure allocations and stuff, but compared with the typical Haskell list-processing programs I don't see any significantly larger overhead.
  - foota 7y ago
    I don't know that I would ever do this, since O(lgn) space is normally trivial, but couldn't you use a RNG that's based on like the depth and start position of a given "stack frame" of a recursion-less quicksort? Like to "recurse" (not actually recurse, but pretend) you would increment depth, the update the start position, and calculate the new partition index based on the (depth, start) tuple? And run that in reverse for going back up the stack. edit: Hah. This is fun. There's a variant where you do tricks with the elements of the array to get constant space. https://link.springer.com/chapter/10.1007/BFb0016252 https://link.springer.com/chapter/10.1007/BFb0016252 The idea is that you partition the elements, but then instead of storing the bounds of the left and right sides, you switch the element from the start of the right side with the partition element of the "stack frame" above you. This later serves as a flag indicating the end of the right side, since the partition of the parent "stack frame" is greater than all elements on the right you know you've hit then end of the right side when you see a larger number than the parent "stack frame"'s pivot.
omidmnzadeh 7y ago
The problem with this piece of code is not that it doesn't do it in-place. The problem is, if the input list is (almost) constant, then this code will (almost) certainly take quadratic time to sort it, even if it is shuffled before being fed to this function. However, I get what you mean. It really is beautiful! EDIT: grammar.
undreren 7y ago
When it comes to Haskell, this function that generates all the fibonacci numbers did it for me: fibs = 0 : scanl (+) 1 fibs
- xwowsersx 7y ago
  Another beaut!
Nemerie 7y ago
Though it's not true quicksort, it's possible to explain the idea of this algorithm with code like this in just a few minutes while the truest implementation in C with Hoare partition looks really confusing
jerome-jh 7y ago
Haskell blows your mind whatever ;)

by switz 7y ago

ridiculous_fish 7y ago

Unfortunately it's also incorrect! It discards NaNs, as they are neither < nor >=.

fulafel 7y ago
I would argue that this is better than most alternatives.
maweki 7y ago
In the example there was no talking about floating point numbers. The ordered type _has_ a total ordering as shown by the Ord typeclass restriction.

hyperpallium 7y ago

I saw a similar version in erlang (in Joe Armstrong's Programming Erlang) and agree it beautifully illustrates the concept of quicksort. Apparently, Tony Hoare came up with it when he took a class teaching him recursion (i.e. he was a student). But the flaw you note unfortunately undermines performance... the "quick" in "quicksort". Thus, IMHO it's a compelling illustration of the profound strengths and weaknesses of fp.

0b01 7y ago

This may be an elegant piece of code at first glance except the niceties of quicksort such as cache locality and stability come entirely from the in-placeness of the partition procedure.

fdsdsa_7777 7y ago

I won't comment on how quicksort-y this is, but the combination of pattern matching and recursion is bread-and-butter Haskell. A number of seemingly complex algorithms can be implemented in a similar way. Having said that, it is elegant and clean and -- taken by itself -- does make Haskell very attractive.

xwowsersx 7y ago

Agreed that this is beautiful purely from the standpoint of how there is essentially no disconnect between the concept of the algorithm and the way it's expressed in code. It's almost the math/algo just translated directly into code (not commenting on the efficiency or other issues that may exist).

nwallin 7y ago

Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of quick sort, it's straight up bad. This implementation of quicksort is actually a great example of why functional programming sucks. It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption. So a normal programmer might sort via quicksort in Haskell because it's the optimal sort in imperative languages even though naive Haskell quicksort is objectively worse in every way than naive Haskell mergesort. Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++. And that's a very low bar.

kccqzy 7y ago
> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n) space. Use of randomization would result in a high probability of choosing a good pivot element, but even then you can expect approximately O(log n) space. Also would like to see why you think the Haskell version has enormous constant time overhead. Where do you think this overhead comes from? If you are comparing to an equivalent program in C++ then sure allocations and stuff, but compared with the typical Haskell list-processing programs I don't see any significantly larger overhead.
- foota 7y ago
  I don't know that I would ever do this, since O(lgn) space is normally trivial, but couldn't you use a RNG that's based on like the depth and start position of a given "stack frame" of a recursion-less quicksort? Like to "recurse" (not actually recurse, but pretend) you would increment depth, the update the start position, and calculate the new partition index based on the (depth, start) tuple? And run that in reverse for going back up the stack. edit: Hah. This is fun. There's a variant where you do tricks with the elements of the array to get constant space. https://link.springer.com/chapter/10.1007/BFb0016252 https://link.springer.com/chapter/10.1007/BFb0016252 The idea is that you partition the elements, but then instead of storing the bounds of the left and right sides, you switch the element from the start of the right side with the partition element of the "stack frame" above you. This later serves as a flag indicating the end of the right side, since the partition of the parent "stack frame" is greater than all elements on the right you know you've hit then end of the right side when you see a larger number than the parent "stack frame"'s pivot.

omidmnzadeh 7y ago

The problem with this piece of code is not that it doesn't do it in-place. The problem is, if the input list is (almost) constant, then this code will (almost) certainly take quadratic time to sort it, even if it is shuffled before being fed to this function. However, I get what you mean. It really is beautiful! EDIT: grammar.

undreren 7y ago

When it comes to Haskell, this function that generates all the fibonacci numbers did it for me: fibs = 0 : scanl (+) 1 fibs

xwowsersx 7y ago
Another beaut!

Nemerie 7y ago

Though it's not true quicksort, it's possible to explain the idea of this algorithm with code like this in just a few minutes while the truest implementation in C with Hoare partition looks really confusing

jerome-jh 7y ago

Haskell blows your mind whatever ;)