Lispで挿入ソート・完

Lispで挿入ソート・その2 - Shammerismで改良したinsert-elementを使用してinsert-sort関数を書いてみた。並べ替え条件と、元リストを渡せばソートした結果を返してくれる、という動き。

? (defun insert-sort (test org)
  (format t "Original List is ~A~%" org)
  (let ((result nil))
    (dolist (x org)
      (setf result (insert-element test x result)))
    result))
INSERT-SORT
? (insert-sort #'< (get-random-list 10))
Original List is (91 5 93 83 35 38 81 84 30 4)
(4 5 30 35 38 81 83 84 91 93)
? 

これを再帰にしたい。どうすればいいだろうか。処理の流れを抽象化すると、対象要素Xを取り出し、Xを残りのリストのどこかに入れる。そして、Xを取り出すたびに残り要素は少なくなるので、Xはcarで残り要素がcdrだ。 上の例でわかるが、中心になるのはinsert-elementだ。再帰の書き方の定型は、終了部分と再帰呼出しを含む中心処理に分割できる。繰り返しになるが、再帰呼出しを含む中心処理は、上の繰り返しの例からinsert-elementとなるので、insert-elementの引数を決定する際に再帰呼び出しを使用する感じだ。

? (defun recursive-insert-sort (test org)
  (format t "Original List is ~A~%" org)
  (if (null org)
      nil
    (insert-element test (car org) (recursive-insert-sort test (cdr org)))))
RECURSIVE-INSERT-SORT
? (recursive-insert-sort #'< (get-random-list 10))
Original List is (39 16 31 95 26 93 27 38 57 42)
Original List is (16 31 95 26 93 27 38 57 42)
Original List is (31 95 26 93 27 38 57 42)
Original List is (95 26 93 27 38 57 42)
Original List is (26 93 27 38 57 42)
Original List is (93 27 38 57 42)
Original List is (27 38 57 42)
Original List is (38 57 42)
Original List is (57 42)
Original List is (42)
Original List is NIL
(16 26 27 31 38 39 42 57 93 95)
?