government / examples / quicksort.gov.lisp

@ 202aec8d6f143ace005fbbe41cc33c7a6344995e | history


; quicksort.gov.lisp: sort a list of numbers.
;
; There are no loops and no mutation, so everything is recursion over
; lists. Definitions are sequential, so each helper comes before the
; functions that use it.

(define append
  (lambda (a b)
    (if (== a '())
        b
        (cons (car a) (append (cdr a) b)))))

; filter keeps the elements of l for which (keep x) is true.
(define filter
  (lambda (keep l)
    (if (== l '())
        '()
        (if (keep (car l))
            (cons (car l) (filter keep (cdr l)))
            (filter keep (cdr l))))))

; Partition around the first element, sort each side, and join them. The
; inner lambda binds pivot and rest; the two lambdas passed to filter are
; closures over pivot.
(define quicksort
  (lambda (l)
    (if (== l '())
        '()
        ((lambda (pivot rest)
           (append (quicksort (filter (lambda (x) (< x pivot)) rest))
                   (cons pivot (quicksort (filter (lambda (x) (>= x pivot)) rest)))))
         (car l)
         (cdr l)))))

(quicksort '(3 1 4 1 5 9 2 6 5 3 5))
(quicksort '(2.5 -1 0 7 -3.25))