lisp の quicksort

まぁ、まだ元気だよ。と言うことで、とっても久しぶり。

年に一度位。歳と共に頻度が少なくなる気がするけど SICP を中途半端なまま眺めたりすることがある。少し前くらいかな。関数型言語が流行ったらしくていくつか入門書らしきものも購入したり。その中に Haskell の quick ソートがあった。3.1 Quicksort in Haskell

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

すんごいシンプル。

• 遅延評価
• 副作用はモナドが引き受ける

あたりが魅力的。同じようなものは...と探したところ、Lisp のものもあった。swisspig.net - The Beauty of a Lisp Quicksort

(defun quicksort (lis) (if (null lis) nil
  (let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (< a x))))
    (append (quicksort (remove-if-not fn r)) (list x)
      (quicksort (remove-if fn r))))))

で、拙い Scheme では....

(use srfi-1)

(define (qsort lst)
  (if (null? lst) '()
      (let* ((x (car lst))
             (r (cdr lst)))
        (append
         (qsort (filter (lambda (a) (< a x)) r))
         (list x)
         (qsort (filter (lambda (a) (>= a x)) r))))))

さらに Shiro さん の続きを早く読みたい なんでも継続を眺めつつ.... こんな感じなのかなぁ。

(define (qsort/cps lst cont)
  (if (null? lst) (cont '())
      (let* ((x (car lst))
             (r (cdr lst)))
        (qsort/cps (filter (lambda (a) (< a x)) r)
                   (lambda (n)
                     (qsort/cps (filter (lambda (a) (>= a x)) r)
                                (lambda (m) (cont (append n (list x) m)))))))))

メジャーどころの Python でも同じようにするには、こんなん?

def qsort(lst):
    if len(lst) < 1: return []

    x = lst[0]
    r = lst[1:]

    return qsort([i for i in r if i < x]) \
           + [x] \
           + qsort([i for i in r if i >= x])