Just prowling around today, I found a couple interesting pages on Haskell. I am thinking about trying it out a bit, just to see what I can learn. At any rate, on one of the intro documents I found the following code snippet:
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
(135 chars)
“Wow,” I thought. That’s pretty cool. Especially compared to the C version on the same page (451 chars). That one brought back memories of coding merge sort as a freshman at Tech.
So I got to thinking… what does quicksort look like in Common Lisp? I googled a bit, and found some code here(549 chars!) and here(376 chars!). I’m sure they are quite efficient, but for the purposes of my little journey, they failed miserably — too verbose!
So here is the best I can come up with — I am sure that there is a shorter way, but this sufficies:
(defun qsort (lst) (if lst (let ((f #'(lambda (y) (> y (car lst))))) `(,@(qsort (remove-if f (cdr lst))) ,(car lst) ,@(qsort (remove-if-not f (cdr lst))))) '()))
Down to 190 chars.
I could move a couple lines up and cheat, but I think it’s good for now.