リストの破壊的修正
今まで説明したリスト操作関数は、引数のリストを直接修正せずに新しいリストを生成して返しています。たとえば、append で (A B C) と (D E F) を連結する場合、最初の引数 (A B C) はそのままで、2 つのリストを連結した新しいリスト (A B C D E F) を作っています。つまり、(A B C) はコピーされるわけです。また、リストを修正する列関数 remove や substitute でも、引数のリストを修正せずに新しいリストが生成されます。
このように、リストを操作する関数の多くが新しいリストを生成して返しますが、プログラムによっては引数のリストを直接修正 (破壊的修正) した方が便利な場合もあります。今回は Common Lisp に用意されているリストを破壊的に修正する関数を説明します。
●リスト構造の修正
Lisp の基本 で説明したように、リストは複数のコンスセルを接続して構成されています。コンスセルにはデータを格納する CAR とコンスセルをつなぐ CDR という場所があります。Lisp にはコンスセルの CAR 部を直接書き換える関数 rplaca と、CDR 部を直接書き換える関数 rplacd が用意されています。
rplaca cell object rplacd cell object
rplaca はコンスセル cell の CAR 部を object に書き換えます。cell にリストが与えられた場合は、先頭のコンスセルの CAR 部を書き換えます。rplaca は書き換えた cell を返します。簡単な例を示しましょう。
* (setq z '(a b c)) (A B C) * (rplaca z 'd) (D B C)
変数 Z に (A B C) をセットします。rplaca はコンスセルの CAR 部、この場合は (A B C) の先頭セルの CAR 部を A から D に書き換えます。リストの CAR 部を直接書き換えるので、変数 Z の値も (D B C) になることに注意してください。次の図を見てください。
上図に示すように、変数 Z はリスト (A B C) を格納しています。rplaca は変数 Z が格納しているコンスセルの CAR 部を直接 D に書き換えるので、変数 Z の値も (D B C) になるのです。このように、rplaca には副作用があるので使用には十分な注意が必要です。
rplacd はコンスセル cell の CDR 部を object に変更します。cell にリストが与えられた場合は、先頭のコンスセルの CDR 部を書き換えます。rplacd は書き換えた cell を返します。簡単な例を示しましょう。
* (setq z '(a b c)) (A B C) * (rplacd z 'd) (A . D)
rplacd はコンスセルの CDR 部、この場合は (A B C) の先頭セルの CDR 部を D に書き換えます。次の図を見てください
上図に示すように、CDR 部にはコンスセルがつながっていますが、それをシンボル d に書き換えるのですから後ろのコンスセルは切断されて、変数 z の値は (a . d) というドット対になります。rplacd にも副作用があることに注意してください。
rplaca と rplacd は初期の Lisp からある関数です。Common Lisp にも用意されていますが、実際に使うことはあまりないと思います。というのも、リストの破壊的修正は setf で行うことができるからです。car や cdr などリストの要素にアクセスする関数は汎変数として使用することができます。(rplaca z 'd) は (setf (car z) 'd) と同じで、(rplacd z 'd) は (setf (cdr z) 'd) と同じです。簡単な例を示しましょう。
* (setq z '(a b c)) (A B C) * (setf (car z) 'd) D * z (D B C) * (setf (cdr z) 'e) E * z (D . E)
このほかにも、setf は first, second, ..., tenth, rest, nth や列関数 elt などと組み合わせることで、リストの内容を直接書き換えることができます。次の図を見てください。
(first z) の代わりに (elt z 0) や (nth 0 z) を使うことができます。このように、書き換えるリストの位置をアクセス関数で指定するわけです。
●リストの連結
リストを連結する関数に append がありますが、引数のリストは破壊されません。append の動作を図 (再掲) に示します。
このように append は第 1 引数のリストをコピーしてから連結します。これに対し、引数のリストをコピーせずに連結する関数が nconc です。
nconc &rest lists
関数 nconc は引数のリストをつなぎあわせたリストを返します。最後を除く引数の内容が破壊されます。次の図を見てください。
上図に示すように、nconc はリストの最終セルの CDR 部を直接書き換えることで、引数のリストを連結しています。簡単な例を示しましょう。
* (setq x '(a b c)) (A B C) * (setq y '(d e f)) (D E F) * (nconc x y) (A B C D E F) * x (A B C D E F) * y (D E F)
変数 X と Y に格納されているリストを nconc で連結します。このとき、変数 X の値は書き換えられることに注意してください。
●mapcan と mapcon
関数 mapcan と mapcon はマッピングしたあとの結果 (リスト) を nconc で連結します。次式と同じ動作になります。
(mapcan fn xs) ≡ (apply #'nconc (mapcar fn xs)) (mapcon fn xs) ≡ (apply #'nconc (maplist fn xs))
簡単な使用例を示します。
* (mapcar (lambda (x) (list x x)) '(a b c d e)) ((A A) (B B) (C C) (D D) (E E)) * (apply #'nconc (mapcar (lambda (x) (list x x)) '(a b c d e))) (A A B B C C D D E E) * (mapcan (lambda (x) (list x x)) '(a b c d e)) (A A B B C C D D E E) * (maplist (lambda (xs) (copy-list xs)) '(a b c d e)) ((A B C D E) (B C D E) (C D E) (D E) (E)) * (apply #'nconc (maplist (lambda (xs) (copy-list xs)) '(a b c d e))) (A B C D E B C D E C D E D E E) * (mapcon (lambda (xs) (copy-list xs)) '(a b c d e)) (A B C D E B C D E C D E D E E)
mapcan はマッピングしたあとでリストを平坦化する動作になります。これは 関数 flatmap と同じです。flatmap は レキシカルスコープとクロージャ の問題 1 で取り上げました。リストを再掲します。
リスト : マッピングしたあと平坦化する (再掲) (defun flatmap (func xs) (apply #'append (mapcar func xs)))
flatmap は append を使ってリストを連結しますが、mapcan は nconc を使ってリストを破壊的に連結するところが異なります。mapcon もそうですが、マッピングの結果を破壊できない場合もあるので、使用するときには十分に注意してください。
●リストの反転
関数 reverse はリストの要素を逆順にした新しいリストを生成して返します。ここで、リストを破壊的に修正する関数 nreverse を考えてみましょう。Common Lisp の場合、破壊的な操作を行う関数名には先頭に n を付けることが多いです。nreverse は Common Lisp に用意されていますが、私たちでもプログラムすることができます。次の図を見てください。
変数 XS に格納されたリストを逆順にします。このとき、変数 R に逆順のリストを保持します。考え方は簡単です。リストの先頭から要素を順番に取り出して、変数 R のリストに追加していくところは reverse と同じです。この操作をセルをつなぎかえることで行っているのが nreverse です。つまり、セルごと要素を移動しているのです。
これをプログラムすると次のようになります。
リスト : リストの反転 (破壊的操作)
(defun my-nreverse (xs &optional r)
(if (null xs)
r
(my-nreverse (cdr xs) (rplacd xs r))))
関数名は my-nreverse としました。オプショナル引数 R に逆順のリストを保持します。引数 XS が空リストの場合は R を返します。そうでなければ、my-nreverse を再帰呼び出しします。このとき、(cdr xs) で次のセルを渡して、(rplacd xs r) で先頭セルの CDR 部に R を連結します。rplacd はセルを返すので、引数 R には逆順のリストが渡されることになります。
なお、このプログラムは (cdr xs) と (rplacd xs r) を評価する順番が逆になると動作しません。Common Lisp の場合、引数は左から右に (リストの先頭から順番に) 評価されることが仕様で定められているので、このままで正しく動作します。他のプログラミング言語、たとえば Scheme の仕様 (R5RS) [*1] では規定されておらず処理系に依存します。Common Lisp 以外の言語に移植する場合、引数を右から左へ評価する処理系では正しく動作しないので注意してください。
それでは簡単な例を示しましょう。
* (setq x '(a b c d e)) (A B C D E) * (setq y (my-nreverse x)) (E D C B A) * x (A) * y (E D C B A)
my-nreverse の返り値を代入した変数 Y の値は逆順のリストになっています。ところが、変数 X の値は逆順のリストになっていません。my-nreverse は変数 X のリストを破壊的に修正しますが、変数 X の値が逆順のリストになるわけではありません。これは Common Lisp の関数 nreverse でも同じです。ご注意くださいませ。
[*1] R5RS は少し古い仕様です。M.Hiroi が理解しているのは R5RS までで、新しい仕様 (R6RS, R7RS) はわかりません。
●リスト操作関数の改良
高階関数とラムダ式 で作成したマップ関数 map1 と map2 や ラムダリストキーワード で出題したマップ関数 mapn は、再帰定義でプログラムしていますが末尾再帰ではないので、長いリストを渡すとスタックオーバーフローする恐れがあります。次の例を見てください。
リスト : マップ関数 (再掲)
(defun map1 (fn xs)
(if (null xs)
nil
(cons (funcall fn (car xs))
(map1 fn (cdr xs)))))
* (length (map1 #'identity (make-list 10000))) 10000 * (length (map1 #'identity (make-list 100000))) => エラー "Control stack exhausted (no more space for function call frames)."
ここで nreverse を使うと、コンスセルの消費量は同じままで、再帰定義を繰り返し (末尾再帰) に変換することができます。ただし、nreverse の処理が加わるので、実行時間は余分にかかることになります。ようするに、実行効率には目をつぶって堅牢性を優先するわけです。
プログラムは次のようになります。
リスト : マップ関数 (改良版)
(defun map1 (fn xs &optional zs)
(if (null xs)
(nreverse zs)
(map1 fn (cdr xs) (cons (funcall fn (car xs)) zs))))
(defun map2 (fn xs ys &optional zs)
(if (or (null xs) (null ys))
(nreverse zs)
(map2 fn (cdr xs) (cdr ys) (cons (funcall fn (car xs) (car ys)) zs))))
(defun mapn (fn &rest args)
(do ((zs nil)
(xs args (map1 #'cdr xs)))
((member nil xs) (nreverse zs))
(push (apply fn (map1 #'car xs)) zs)))
map1 と map2 は末尾再帰で、mapn は do ループでプログラムしています。どの関数も変数 ZS に関数 FN の返り値を追加 (プッシュ) して、最後に nreverse で ZS を反転して返します。これで長いリストでもスタックオーバーフローすることはありません。簡単な実行例を示します。
* (length (map1 #'identity (make-list 10000))) 10000 * (length (map1 #'identity (make-list 100000))) 100000 * (length (map2 #'list (make-list 10000) (make-list 10000))) 10000 * (length (map2 #'list (make-list 100000) (make-list 100000))) 100000 * (length (mapn #'list (make-list 10000) (make-list 10000) (make-list 10000))) 10000 * (length (mapn #'list (make-list 100000) (make-list 100000) (make-list 100000))) 100000
同様の方法で、関数 filter, take, take-while も堅牢性を高めることができます。
リスト : リスト操作関数
;;; フィルター
(defun filter (pred xs &optional zs)
(cond
((null xs) (nreverse zs))
((funcall pred (car xs))
(filter pred (cdr xs) (cons (car xs) zs)))
(t (filter pred (cdr xs) zs))))
;;; リストの先頭から n 個の要素を取り出す
(defun take (xs n &optional zs)
(if (or (null xs) (zerop n))
(nreverse zs)
(take (cdr xs) (1- n) (cons (car xs) zs))))
;;; 述語 pred が真を返す間、リストから要素を取り出す
(defun take-while (pred xs &optional zs)
(if (or (null xs) (not (funcall pred (car xs))))
(nreverse zs)
(take-while pred (cdr xs) (cons (car xs) zs))))
簡単な実行例を示します。
* (filter #'evenp '(1 2 3 4 5 6 7 8 9 10)) (2 4 6 8 10) * (take '(1 2 3 4 5 6 7 8 9 10) 5) (1 2 3 4 5) * (take-while (lambda (x) (<= x 5)) '(1 2 3 4 5 6 7 8 9 10)) (1 2 3 4 5)
長いリストでの動作確認は皆さんにお任せいたします。実際にいろいろ試してみてください。
●リストの置換
入れ子になっているリスト構造を「木 (tree)」といいます。関数 subst は木の要素を置換しますが、引数の木は破壊しないで新しい木を生成します。引数の木を破壊的に置換する関数が nsubst です。
| 関数名 | 機能 |
|---|---|
| nsubst new old tree | old と等しい要素を new に置き換える |
| nsubst-if new predicate tree | predicate が真となる要素を new に置き換える |
| nsubst-if-not new predicate tree | predicate が偽となる要素を new に置き換える |
nsubst は、リスト tree の old に等しい (eql) 部分を、new に破壊的に置き換えます。nsubst はリストの構造を再帰的にたどり、すべての要素を検査します。簡単な例を示しましょう。
* (setq x '(a b c (a b c (a b c . a)))) (A B C (A B C (A B C . A))) * (nsubst 1 'a x) (1 B C (1 B C (1 B C . 1))) * x (1 B C (1 B C (1 B C . 1))) * (setq y '(((1 2) (3 4)) (5 6))) (((1 2) (3 4)) (5 6)) * (nsubst-if 0 (lambda (x) (and (integerp x) (evenp x))) y) (((1 0) (3 0)) (5 0)) * y (((1 0) (3 0)) (5 0))
nsubst-if, -if-not を使う場合、subst-if, -if-not と同様に述語にはリストも渡されるので、最後の例は #'evenp だけでは動作しません。つまり、1 や 2 だけではなく、(1 2) や ((1 2) (3 4)) も検査されるのです。ご注意ください。
nsubst, -if, -if-not はキーワード :key を指定することができます。それから、nsubst は :test と :test-not も指定することができます。
●循環リスト
リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list)」といいます。次の図を見てください。
リスト (1 2 3) は NIL で終端されています。このリストで、最後尾のセルの CDR 部を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。それでは、実際に循環リストを作ってみましょう。
* *print-circle* NIL * (setq *print-circle* t) T * (setq z '(1 2 3)) (1 2 3) * (setf (cdddr z) z) #1=(1 2 3 . #1#) * (dotimes (x 6) (print (car (nthcdr x z)))) 1 2 3 1 2 3 NIL
循環リストを print などで表示しようとすると、(1 2 3 1 2 3 ... のように人が手動で中断しない限り止まらなくなります。この場合、スペシャル変数 *print-circle* の値を真にすると、print でも循環リストを表示することができます。
(setf (cdddr z) z) とすると、最後尾のセルの CDR 部を先頭のセルに書き換えます。循環リストは #1=(1 2 3 . #1#) と表示されます。最後の例のように、(nthcdr x z) で x に大きな整数を与えても、リストをグルグル回るだけで終端に到達することはありません。
Common Lisp では、#n= により Lisp データにラベルを付けることができます。n には整数値を指定し、#n# でそのデータを参照することができます。#1=(a b c . #1#) の場合、#1= で先頭のセルにラベルがつけられ、最後尾のセルの CDR 部で先頭のセルを #1# で参照しています。これで循環リストを表すことができます。
また、#n= と #n# はプログラムで使うことができます。たとえば、(setq z '#1=(1 2 3 . #1#)) とすれば、循環リストを生成して変数 z にセットすることができます。ほかの例も示しましょう。
* (setq a '("abc" "abc"))
("abc" "abc")
* (setq b '(#1="abc" #1#))
(#1="abc" #1#)
* (eq (first a) (second a))
NIL
* (eq (first b) (second b))
T
Lisp の場合、リスト ("abc" "abc") の 2 つの文字列 "abc" は別々のデータとして生成されるのが普通です。したがって、2 つの文字列を eq で比較すると NIL になります。ところが (#1="abc" #1#) とすると、最初の文字列にラベルが付けられて次の要素でその文字列を参照しているので、リストは同一の文字列データを格納することになります。よって、リストの第 1 要素と第 2 要素を eq で比較すると T になります。
●循環リストのチェック
循環リストに関数 length を適用すると無限ループになるかもしれませんが、関数 list-length は循環リストを検出すると NIL を返します。
list-length list
簡単な使用例を示します。
* (list-length '#1=(a b c . #1#)) NIL * (list-length nil) 0 * (list-length '(a)) 1 * (list-length '(a b c d)) 4
循環リストのチェックは「うさぎとかめ」のアルゴリズムを使うと簡単です。「うさぎ」と「かめ」はリストをたどる変数として定義します。うさぎは cdr を 2 回適用して進みますが、かめは cdr を 1 回適用して進みます。うさぎがリストの終端に到達すれば、リストは循環していないことがわかります。うさぎがかめに追いつけば、リストは循環していると判断できます。プログラムは次のようになります。
リスト : 循環リストのチェック
(defun circular-list-p (xs)
(let ((fast xs) (slow xs))
(loop
(setq fast (cddr fast)
slow (cdr slow))
(cond ((endp fast) (return))
((eq fast slow) (return t))))))
変数 FAST が「うさぎ」で SLOW が「かめ」を表します。FAST は cddr で、SLOW は cdr で進みます。FAST が終端に到達すれば循環リストではありません。return で loop から脱出して NIL を返します。「うさぎ」が「かめ」に追いつくと FAST と SLOW の値は同じセルになるので、(eq fast slow) の評価結果は真になります。(return t) で loop から脱出して T を返します。
それでは実際に試してみましょう。
* (circular-list-p '#1=(a b c . #1#)) T * (circular-list-p nil) NIL * (circular-list-p '(a)) NIL * (circular-list-p '(a b c d)) NIL
正常に動作していますね。今回は簡単に繰り返しでプログラムを作りましたが、興味のある方は再帰定義でもプログラムを作ってみてください。