Programming languages have become more expressive over time. Consider quicksort. Hoare's original version was quite difficult to understand - IIRC it wasn't even recursive. Nowadays the two-line quicksort is an icon of Haskell:
qs  =  qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (>= x) xs)
Unfortunately it's also an icon of unrealistic examples - it makes too many passes over the lists, and conses far too much, so it isn't all that quick. The more efficient sorts don't make such impressive examples - especially the destructive ones, whose Haskell incarnations are infested with intimidating monads.
Here's a gem from the Pitmanual: a reasonably clear destructive quicksort in fifteen lines.
Date: 9 September 1981 18:44-EDT From: George J. Carrette <GJC> To: KMP cc: JAR I think that the QUICKSORT properly coded is even shorter and neater than the BUBBLESORT. It is also better for showing students since it is naturally recursive, divide&conquer.
(defmacro rplacd&pop (x &optional y) `(rplacd (prog1 ,x (setq ,x (cdr ,x))) ,y)) (defun quicksort (list judge) (if (null list) () (do ((proof (rplacd&pop list)) (goats ()) (sheep ())) ((null list) (nconc (quicksort goats judge) proof (quicksort sheep judge))) (if (funcall judge (car list) (car proof)) (setq goats (rplacd&pop list goats)) (setq sheep (rplacd&pop list sheep))))))
rplacd&pop captures the idea of destructively removing the first element of a list. It sounds like a nice example, since it uses a macro to express a by-reference operation in a language without by-reference parameters. But it's not really good for showing students, because it's not safe - it evaluates x twice and its subforms (if any) thrice. (Update 6 April: it uses
setf, so it's ok in Maclisp, because it only works on variables. Even in Common Lisp it would only be a problem when used with a symbol-macro.) I don't know how to do it right in Maclisp, but in Common Lisp it requires the sort of macrology that inspires fear and loathing:
(defmacro rplacd&pop (x &optional y &environment e) (multiple-value-bind (temps forms svars writeform readform) (get-setf-expansion x e) `(let* (,@(mapcar #'list temps forms) (,(car svars) (cdr ,readform))) (prog1 ,readform (setf (cdr ,readform) ,y) ,writeform))))
This might be a good example of how to write
setf-like macros, which is a confusing corner of Common Lisp that certainly deserves some examples. But it's no way to write a clear quicksort!
Of course, the simplest way for a language to make a realistic quicksort simple is to predefine
partition. Is that cheating? I think it could be useful often enough to belong in a standard library. But to truly simplify quicksort down to a one-liner will require some advances in expressiveness, so we can write something closer to the natural definition: partition on the first element and recurse on both halves.