Hacker News Reader

Comment by bayareaguy | Hacker News Reader

My vote for the most beautiful quicksort is this Haskell one:

  module Quicksort where

  quicksort (x:xs) = 
      quicksort [ i | i <- xs, i < x ] 
      ++ [x] ++
      quicksort [ i | i <- xs, i >= x ]

  quicksort [] = []

View on HN

You're doing two filters with list comprehensions which you could switch with one span:

    quicksort (x:xs) = let (a, b) = span (< x) xs in (quicksort a) ++ [x] ++ (quicksort b)

You're doing two filters with list comprehensions which you could switch with one span:

    quicksort (x:xs) = let (a, b) = span (< x) xs in (quicksort a) ++ [x] ++ (quicksort b)

Actually, this is incorrect. span will split the list as soon as it finds the predicate to be false on an item, instead of finding the smaller elements of the whole list. So, for instance, if we try your function as in the following, we get improper results:

  > quicksort [1, 2, 3, 2, 1]
  [1,2,1,2,3]
  > quicksort [1, 2, 3, -2, -1]
  [1,2,-2,-1,3]
  > quicksort [1, 2, 3, -2, 0, -1]
  [1,2,-2,-1,0,3]

Serves me right, should have tested the code before I submitted it. Just s/span/partition/ and it should work.

Nearly identical implementation in Erlang:

  qsort([]) -> [];

  qsort([Pivot|Rest]) ->
    qsort([ X || X <- Rest, X < Pivot]) 
    ++ [Pivot] ++ 
    qsort([ X || X <- Rest, X >= Pivot]).

More: http://en.literateprograms.org/Category:Quicksort

In this paper they show how to do something like this in CL. http://rali.iro.umontreal.ca/Publications/urls/LapalmeLispCo...

  (defun qsort (ax)
    (and ax
         (let ((a (car ax))
               (x (cdr ax)))
           (append (qsort [y (y <- x) (< y a)])
                   (list a)
                   (qsort [y (y <- x) (>= y a)])))))

If you want the x:xs stuff you could load fare-matcher and write something like:

  (defun qsort (l)
    (ematch l
      (nil nil)
      ((cons x xs) (append (qsort [ i (i <- xs) (< i x) ])
                           (list x)
                           (qsort [ i (i <- xs) (>= i x) ])))))

A more clear and equally useless code:

  qsort [] = []
  qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Wow. That's so beautiful and elegant! Thanks for sharing! I added it to my article!

It's also too inefficient to belong anywhere in the vicinity of working code.

Beautiful, elegant, useless. Maybe that should be the Haskell motto.

Reply on news.ycombinator.com