Re:Learn Haskell in minutes
by octo_t on Monday July 01, 2013 @08:03AM
(#5970023)
Technically the quicksort at the end of the tutorial isn't idiomatic quicksort, the memory complexity is wrong.
[ Parent
| on HN ]
Re:Learn Haskell in minutes
by egonschiele on Monday July 01, 2013 @12:18PM
(#5971608)
Correct. Sadly explaining monads and mutable data in Haskell would make this guide a lot longer. The example I gave is the traditional "look has elegant Haskell is!" example, not the "look how fast Haskell is!" example :)
Re:Learn Haskell in minutes
by DanWaterworth on Tuesday July 02, 2013 @08:24AM
(#5977304)
You could use mergesort instead:
merge :: Ord x => [x] -> [x] -> [x]
merge [] y = y
merge x [] = x
merge (x:xs) (y:ys) =
if x < y then
x:(merge xs (y:ys))
else
y:(merge (x:xs) ys)
odds :: [x] -> [x]
odds [] = []
odds (x:xs) = x:(evens xs)
evens :: [x] -> [x]
evens = odds . drop 1
mergesort :: Ord x => [x] -> [x]
mergesort [] = []
mergesort [x] = [x]
mergesort x = merge (mergesort (odds x)) (mergesort (evens x))Even for linked lists, which is how [] is defined in Haskell?
I believe the idea is that if it is not "in place," it is not quick sort.
That's right. That Haskell faux-quicksort uses a lot of extra space for the temporary lists.
Here's a Haskell version of the "real" quicksort, though it isn't nearly easy a read as the faux-quicksort:
http://augustss.blogspot.jp/2007/08/quicksort-in-haskell-qui...
For what is worth, the standard Haskell sort is a variant of merge sort.
http://hackage.haskell.org/packages/archive/base/latest/doc/...