How to remove redundancy in Lisp code?

Question

I tried to implement quicksort in Common Lisp, and this is what I got so far:

(defun quick-sort (list) (if (cdr list) (let ((pivot (car list))) (append (quick-sort (remove-if-not (lambda (n) (< n pivot)) list)) (remove-if-not (lambda (n) (= n pivot)) list) (quick-sort (remove-if-not (lambda (n) (> n pivot)) list)))) list)) 

This seems to work, but I think there are too many repetitions in this code. Basically, we have three times:

 (remove-if-not (lambda (n) (< n pivot)) list) 

The only way the three calls differ is - > vs = vs < .

So my question is: how can I remove this redundancy and make the code more readable and more compact?

Of course, I could extract things into a function, for example:

 (defun which (operator pivot list ) (remove-if-not (lambda (n) (funcall operator n pivot)) list)) (defun quick-sort (list) (if (cdr list) (let ((pivot (car list))) (append (quick-sort (which #'< pivot list)) (which #'= pivot list) (quick-sort (which #'> pivot list)))) list)) 

But for some reason I’m not quite sure that this is the best approach. Still clumsy having to turn in pivot and list again and again.

I also came up with the idea of ​​using flet , which makes the real body of the function more readable, but only moves complexity to another place:

 (defun quick-sort (list) (if (cdr list) (let ((pivot (car list))) (flet ((left () (remove-if-not (lambda (n) (< n pivot)) list)) (middle () (remove-if-not (lambda (n) (= n pivot)) list)) (right () (remove-if-not (lambda (n) (> n pivot)) list))) (append (quick-sort (left)) (middle) (quick-sort (right))))) list)) 

Any other approaches?

Answer 1

If you write it as a local function, you do not need to pass additional arguments, since they are in scope.

 (defun quick-sort (list) (if (rest list) (let ((pivot (first list))) (flet ((filter (operator) (remove-if-not (lambda (n) (funcall operator n pivot)) list))) (append (quick-sort (filter #'<)) (filter #'=) (quick-sort (filter #'>))))) list)) 

A slightly more compact version:

 (defun quick-sort (list &aux (pivot (first list))) (flet ((filter (operator) (remove-if-not (lambda (n) (funcall operator n pivot)) list))) (and list (nconc (quick-sort (filter #'<)) (filter #'=) (quick-sort (filter #'>)))))) 

Since Common Lisp supports multiple values, you can also split the list into one function at a time and return the lists as values:

 (defun partition (list pivot) (loop for e in list when (< e pivot) collect e into smaller else when (> e pivot) collect e into larger else when (= e pivot) collect e into same finally (return (values smaller same larger)))) (defun quick-sort (list) (if (rest list) (multiple-value-bind (smaller same larger) (partition list (first list)) (append (quick-sort smaller) same (quick-sort larger))) list)) 

When lists are just highlighted, perhaps NCONC . Since REMOVE-IF-NOT is non-destructive (compare with DELETE-IF-NOT ), NCONC excellent. As LOOP collects new listings, NCONC again fine.

This is the actual in-place quicksort over vectors. Note that Quicksort actually does. Versions using lists are not really Quicksort.

 (defun partition (array left right &aux (i (1- left)) (j right) (v (aref array right))) (loop do (loop do (incf i) until (>= (aref array i) v)) (loop do (decf j) until (or (zerop j) (<= (aref array j) v))) (rotatef (aref array i) (aref array j)) until (<= ji)) (rotatef (aref array j) (aref array i) (aref array right)) i) (defun quicksort (array &optional (left 0) (right (1- (length array)))) (if (> right left) (let ((i (partition array left right))) (quicksort array left (1- i)) (quicksort array (1+ i) right)) array)) 

This version is based on Sedgewick code.