the zero bit stream

programmer things

Beautiful Quicksort in Common Lisp

Disclaimer: This is Quicksort, just not one you’d use in production. You can see it does twice as many comparisons as necessary, or much worse if it encounters a pre-sorted list. The list manipulation (via ++ or APPEND) is doing more work and using more memory than necessary, even for a purely functional implementation.

Quicksort in Haskell vs. Common Lisp

Haskell apologists often cite how Haskell code is terse and expressive. I’ve used Haskell a bit, and while I do not find its syntax very friendly, it is quite powerful. (As a side note, I really like Standard ML, and I wish I could transplant its eagerness and impurity into Haskell.) Common Lisp is a master of multi-paradigm programming and it wears the functional hat pretty well, too. So, let’s see how it stands up against Haskell.

The canonical “beautiful” Haskell function is the quicksort. Here it is:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

I gotta admit, that’s a pretty good one. Let’s see what it looks like in Common Lisp.

(defun quicksort (list)
  (when list
    (destructuring-bind (p . xs) list
      (let ((lesser (remove-if-not (lambda (x) (< x p)) xs))
            (greater (remove-if-not (lambda (x) (>= x p)) xs)))
        (append (quicksort lesser) (list p) (quicksort greater))))))

I probably wouldn’t write it this way, but this is the closest approximation of what the Haskell function is doing. Let’s break it down into pieces and show which parts correspond in the two examples.

The Haskell code is using pattern matching to deal with the empty list case, and destructuring to split the list into head and tail.

quicksort []     = []
quicksort (p:xs) = expr

The Common Lisp code is using WHEN on the input (which returns NIL for an empty list and otherwise evaluates the expression) and is using DESTRUCTURING-BIND to split the list into head and tail.

(when list
  (destructuring-bind (p . xs) list

Haskell uses “where” to bind local variable in an expression:

... = expr
        binding_a = expr_a
        binding_b = expr_b

Common Lisp uses LET to bind local variables in an expression:

(let ((binding-a expr-a)
      (binding-b expr-b)

Haskell uses partial application of the comparison functions with “filter” to filter the lists.

lesser  = filter (< p) xs
greater = filter (>= p) xs

Common Lisp uses lambdas to construct the filtering closures and REMOVE-IF-NOT which is essentially equivalent to Haskell’s “filter”.

(lesser (remove-if-not (lambda (x) (< x p)) xs))
(greater (remove-if-not (lambda (x) (>= x p)) xs))

Even Terser

OK, but there’s an even shorter, one-line Haskell quicksort.

qsort (p:xs) = qsort [x | x<-xs, x<p] ++ [p] ++ qsort [x | x<-xs, x>=p]

Let’s ignore for now the fact that using 1 and 2 letter variables is a very silly way to write “shorter” code. What’s great about this solution, though, is the use of list comprehensions. Common Lisp doesn’t have list comprehensions, but it doesn’t matter because it has mother-flipping macros, and we can add list comprehensions.

Now, I could pull in a library that gives list comprehensions, but wouldn’t it be funner to write the macro right here?

I’m not going to build a general replacement for all Haskell list comprehensions, just the ones here. I see 4 parts, the value, a binding, a list, and a test. Here’s my first shot at a list comprehension macro:

(defmacro @ (value bind list test)
  (let ((newlist (gensym)))
    `(let ((,newlist nil))
       (dolist (,bind ,list)
         (when ,test
           (push ,value ,newlist)))
       (nreverse ,newlist))))

I selected the @ symbol because it’s short and sweet, and mainly just short. The Haskell folks seem to think 1-letter names are the bees knees, so there you go. A quick test:

;; Something like this in Haskell: [x*2 | x<-[1, 2, 3, 4, 5, 6, 7], x>3]
(@ (* 2 x) x (list 1 2 3 4 5 6 7) (> x 3))
;;-> (8 10 12 14)

In case you don’t know how DEFMACRO works, it takes the input forms, unevaluated and returns a list which is evaluated it its place. You can debug macros to see the intermediate form by just doing the transformation with MACROEXPAND:

(macroexpand '(@ (* 2 x) x (list 1 2 3 4 5 6 7) (> x 3)))
(LET ((#:G791 NIL))
  (DOLIST (X (LIST 1 2 3 4 5 6 7)) (WHEN (> X 3) (PUSH (* 2 X) #:G791)))
  (NREVERSE #:G791))

Alright, armed with our new list comprehension macro, let’s write our super-short quicksort:

(defun qsort (l)
  (when l (destructuring-bind (p . xs) l
            (append (qsort (@ x x xs (< x p))) (list p)
                    (qsort (@ x x xs (>= x p)))))))

That’s pretty good. I still have to use WHEN to deal with the null case which Haskell seems to auto-magically handle, and I still have to use DESTRUCTURING-BIND explicitly. I think it holds up to Haskell’s qsort.

More Generic

Oh, I know, the Haskell qsort function applies to lists of any Ord type, which is to say, any type that can be ordered (or at least implements the proper interface) (disclaimer: I don’t pretend to know Haskell-speak when it comes to Classes, Types, Typeclasses, etc. I got it wrong, I don’t care.). Common Lisp ships with CLOS which provides the ability to create generic methods, but it doesn’t really ship with many implemented interfaces. That could be considered a shortcoming in the language, but more properly, it is a shortcoming in libraries. You can easily define generic methods and implement them on all the types you might want to sort, even types from other packages and libraries.

(defgeneric lt (some other))

(defmethod lt ((some number) (other number)) (< some other))

(defmethod lt ((some string) (other string)) (string< some other))

(defun qsort (l)
  (when l (destructuring-bind (p . xs) l
            (append (qsort (@ x x xs (lt x p))) (list p)
                    (qsort (@ x x xs (not (lt x p))))))))

(qsort (list "this" "is" "only" "a" "test"))
;;-> ("a" "is" "only" "test" "this")

(qsort (list 12/11 -1.09 3000))
;;-> (-1.09 12/11 3000)

So we can be significantly generic with Common Lisp, too. No, it doesn’t have Haskell’s compile time type-checking goodness (or badness, however you want to slice it), it is a fundamentally dynamically typed language. But I think it matches Haskell in expressivity, and what it lacks in terse syntax, it makes up for with flexibility through macros, generic methods, and dynamism.

In conclusion: I love Haskell, please don’t shoot me. Also, Common Lisp is pretty neat, too. Both are definitely worth learning and excellent tools for functional programming.