読者です 読者をやめる 読者になる 読者になる

リストの反転

common lisp

以前に書いたリストを破壊的に反転する関数を少し書き直してみた。
まずは、以前に書いた関数。
参照: nlet

(defun list-reverse! (lst)
  (nlet self ((lst lst) head)
    (if (endp lst)
        head
      (self #1=(cdr lst) (progn (setf #1# head) lst)))))

定義は短いが、progn周りで何をしているのかが一目では分かりにくい。


リストの反転ロジックを確認するために、まずは非破壊的版を書いてみる。

;; リストを反転する方法
;;   1] リスト中の全ての要素を前方から順に辿る
;;   2] 辿った要素をスタックリストに追加する
;;        => スタックには前方から要素が追加されるので、追加(走査)とは逆順に要素が溜まっていく
;;   3] リストの終端に達したら、スタックリストを返す

;; 上のロジックの実装
(defun rev(list &optional head)
  (if (endp list)                  ; 終端チェック
      head                         ; スタックリスト(の先頭)を返す
    (rev (cdr list)                ; 次の要素を辿る
         (cons (car list) head)))) ; 要素をスタックリストに追加する

次に、破壊的版。

(defun rev!(list &optional head)
  (if (endp list)                    ; 終端チェック
      head                           ; スタックリスト(の先頭)を返す
    (rev! (cdr list)                 ; 次の要素を辿る
          (cons! (car list) head)))) ; 要素をスタックリストに追加する

revとconsに'!'がついている以外は、非破壊的版と同様。
cons!の定義は下のようになっている。

;; rev!関数向け
;; 本来はmacroletとして定義するのが望ましいが、見やすくするために定義を分離
(defmacro cons! (car-place list)
  (let ((list-place (second car-place)))  ; car-place = '(car list-place) からリスト名を取り出す
    ;; 以下は、list-reverse!関数でのコードと同様
    ;;
    ;; listAのcdr部に、listBをセットすることは
    ;; listAのcar部を、listBの先頭に追加することに等しい。  ※ '追加'という表現は微妙
    ;;
    ;; ただし、後者の方法では、返されるリスト(コンス)のcdr部が新たに確保されるのに対して、
    ;; 前者では、listAのcdr部が再利用される点が異なる。
    `(progn (setf (cdr ,list-place) ,list)
            ,list-place)))

コメントにある通り、実はrev!とlist-reverse!はやっていることは全く同じ。
単にrev!では、progn周りをマクロとして別な箇所で定義しているだけ。

ただ、このように書くと、非破壊的版と破壊的版の違いがメモリアロケートの方法だけだということがよく分かっておもしろい。