4 ms·

I get a little annoyed when people talk about how _actual_ implementations of algorithms are just a pedantic detail - no. A language that can do neat tricks for

by lolo_ 11y ago

I get a little annoyed when people talk about how _actual_ implementations of algorithms are just a pedantic detail - no. A language that can do neat tricks for a not-actually implementation of an algorithm which a lot of people then blindly take as a great example of its 'elegance', while requiring a lot of ugliness for a _real_ working implementation, is demonstrating something important I think. It reminds me a bit of marketing claims vs. reality for a product.

Almaviva 11y ago
To me it feels like a microcosm of the difference between academic vs pragmatic thinking. The reason to use a quicksort is not because it's elegant and consise, it's because it is fast and memory efficient. When your implementation of an algorithm is actually an algorithm with asymptotically worse memory characteristics, it's not suitable for any real world production code, and this difference is _not_ pedantic. This is what gets me: Haskell articles tend not to stop at presenting this is as a neat and elegant definition of a sort (which it is!) but emphasize that you're a just being picky if you're not willing to brush aside memory usage and reasoning about such in production code.
- mercurial 11y ago
  In my experience, Haskell is not the language you are looking for if you want to reason about runtime memory usage :(
lobster_johnson 11y ago
Blame the people here, not the language. The thing about quicksort is that it is explicitly in-place, something which goes against Haskell's programming model, so the code (if you use mutable vectors) ends up looking like C. It's not a lot worse than the C version, but it is unidiomatic Haskell, and so is considered bad form; much like an implementation of lazy evaluation or monads would look terrible in C. But you probably wouldn't pick quicksort to begin with. People should just stop using it as an example of Haskell's elegance.

by lolo_ 11y ago

Almaviva 11y ago

To me it feels like a microcosm of the difference between academic vs pragmatic thinking. The reason to use a quicksort is not because it's elegant and consise, it's because it is fast and memory efficient. When your implementation of an algorithm is actually an algorithm with asymptotically worse memory characteristics, it's not suitable for any real world production code, and this difference is _not_ pedantic. This is what gets me: Haskell articles tend not to stop at presenting this is as a neat and elegant definition of a sort (which it is!) but emphasize that you're a just being picky if you're not willing to brush aside memory usage and reasoning about such in production code.

mercurial 11y ago
In my experience, Haskell is not the language you are looking for if you want to reason about runtime memory usage :(

lobster_johnson 11y ago

Blame the people here, not the language. The thing about quicksort is that it is explicitly in-place, something which goes against Haskell's programming model, so the code (if you use mutable vectors) ends up looking like C. It's not a lot worse than the C version, but it is unidiomatic Haskell, and so is considered bad form; much like an implementation of lazy evaluation or monads would look terrible in C. But you probably wouldn't pick quicksort to begin with. People should just stop using it as an example of Haskell's elegance.