3 ms·
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...
by bobjones2013 7y ago
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.
- deleted 7y ago[deleted]
- dddbbb 7y agopartition 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.
- gowld 7y agoHaskell 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 https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf