The Beauty of a Lisp Quicksort (Thursday, March 30, 2006)

I have discovered the definition of beauty... last night during a hideous exam for Advanced AI, we were instructed to port a very concise, elegant (if rather inefficient) version of Quicksort from a bizarre obscure programming language called Haskell into a similarly concise, elegant (if rather inefficient) version in Lisp. What I presented for my answer on the exam was good, but I have since come up with a thing of beauty. Quicksort in just a few lines of lisp... it may not be the most efficient, but it has to be the most concise. And it is also the first time in my life, that I have been able to reproduce Quicksort from memory. And here it is:

(defun quicksort (lis) (if (null lis) nil
  (let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (< a x))))
    (append (quicksort (remove-if-not fn r)) (list x)
      (quicksort (remove-if fn r))))))

—Brian (03/30/2006 9:57 AM)