News for hackers. Stuff that matters.
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.
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))
Re:Learn Haskell in minutes by quchen on Monday July 01, 2013 @08:10AM (#5970056)
Even for linked lists, which is how [] is defined in Haskell?
Re:Learn Haskell in minutes by taeric on Monday July 01, 2013 @10:21AM (#5970792)
I believe the idea is that if it is not "in place," it is not quick sort.
Re:Learn Haskell in minutes by nandemo on Monday July 01, 2013 @10:39AM (#5970930)
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/...