bobjones2013's comments

On: Math is an insurance policy

[bobjones2013]

The one liner quicksort implementation in Haskell is only really possible because a good chunk of the hard work was handled by a partition library function... I'm not sure how different that is than just calling quicksort from a library in any other high level language.

[gowld → bobjones2013]

Haskell quicksort isn't quicksort, it's an illustration of quicksort. It's not an in-place constant-memory implementation.

See also the Haskell Sieve of Eratosthenes, which isn't a Sieve of Eratosthenes, and is in fact even slower than naive trial division: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

[dddbbb → bobjones2013]

  partition p xs = foldr (select p) ([],[]) xs
  select p x ~(ts,fs) | p x       = (x:ts,fs)
                      | otherwise = (ts, x:fs)

That is the entirety of `partition` in the standard library.