これまで説明したリスト操作関数は、引数のリストを直接修正せずに新しいリストを生成して返しています。たとえば、append で (a b c) と (d e f) を連結する場合、最初の引数 (a b c) はそのままで、2 つのリストを連結した新しいリスト (a b c d e f) を作っています。つまり、(a b c) はコピーされているわけです。
このように、リストを操作する関数の多くが新しいリストを生成して返しますが、プログラムによっては引数のリストを直接修正（破壊的修正）した方が便利な場合もあります。今回は Scheme に用意されているリストを破壊的に修正する関数を説明します。
Scheme の基礎知識 [1] で説明したように、リストは複数のコンスセルを接続して構成されています。コンスセルにはデータを格納する CAR 部とコンスセルをつなぐ CDR 部という場所があります。Scheme にはコンスセルを直接書き換える関数 set-car! と set-cdr! が用意されています。
set-car! はコンスセル cell の CAR 部を obj に書き換えます。cell にリストが与えられた場合は、先頭のコンスセルの CAR 部を書き換えます。set-car! の返り値は未定義です。簡単な例を示しましょう。
gosh> (define z (list 'a 'b 'c)) z gosh> z (a b c) gosh> (set-car! z 'd) #<undef> gosh> z (d b c)
変数 z にリスト (a b c) をセットします。set-car! はコンスセルの CAR 部、この場合は (a b c) の先頭セルの CAR 部を a から d に書き換えます。リストの CAR 部を直接書き換えるので、変数 z の値も (d b c) になることに注意してください。次の図を見てください。
CAR 部を直接 d に書き換える
│
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ｄ ｂ ｃ
図 : set-car! によるリストの破壊的修正
上図に示すように、変数 z はリスト (a b c) を格納しています。set-car! は変数 z が格納しているコンスセルの CAR 部を直接 d に書き換えるので、変数 z の値も (d b c) になるのです。このように、set-car! には副作用があるので使用には十分な注意が必要です。
set-cdr! はコンスセル cell の CDR 部を obj に書き換えます。cell にリストが与えられた場合は、先頭のコンスセルの CDR 部を書き換えます。set-cdr! の返り値は未定義です。簡単な例を示しましょう。
gosh> (define z (list 'a 'b 'c)) z gosh> z (a b c) gosh> (set-cdr! z 'd) #<undef> gosh> z (a . d)
set-cdr! はコンスセルの CDR 部、この場合は (a b c) の先頭セルの CDR 部を d に書き換えます。次の図を見てください
CDR 部を直接 d に書き換える
│
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・│ │・│・┼─→│・│／│
└┼┴┼┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
ａ ｄ ｂ ｃ
図 : set-cdr! によるリストの破壊的修正
上図に示すように、CDR 部にはコンスセルがつながっていますが、それをシンボル d に書き換えるのですから後ろのコンスセルは切断されて、変数 z の値は (a . d) というドット対になります。set-cdr! にも副作用があることに注意してください。
リストを連結する関数に append がありますが、引数のリストは破壊されません。append の動作を図 (再掲) に示します。
引数 (a b) 引数 (c d)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│／│ ┌→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ │ └┼┴─┘ └┼┴─┘
↓ ↓ │ ↓ ↓
ａ ｂ │ ｃ ｄ
│ │ │
↓ ↓ │
┌┼┬─┐ ┌┼┬─┐ │
┌──│・│・┼─→│・│・┼─┘
│ └─┴─┘ └─┴─┘
│ 新しいセル 新しいセル
↓
append の返り値
(append '(a b) '(c d)) => (a b c d)
図 : append の動作
このように append は第 1 引数のリストをコピーしてから連結します。これに対し、引数のリストをコピーせずに、最後尾のセルの CDR 部を書き換えることで、リストを連結する関数を考えることができます。Common Lisp では nconc と呼ばれている関数ですが、Scheme の仕様書 R5RS にはありません。Gauche (srfi-1) には append! という関数が用意されています。
関数 append! は引数のリストをつなぎあわせたリストを返します。最後を除く引数の内容が破壊されます。次の図を見てください。
引数 (a b) 引数 (c d)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│／┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↑ ↓ ↓
ａ ｂ │ ｃ ｄ
│
CDR 部を直接書き換える
図 : (append! '(a b) '(c d)) の動作
上図に示すように、append! はリストの最終セルの CDR 部を直接書き換えることで、引数のリストを連結しています。簡単な例を示しましょう。
gosh> (define x (list 'a 'b 'c)) x gosh> (define y (list 'd 'e 'f)) y gosh> (append! x y) (a b c d e f) gosh> x (a b c d e f) gosh> y (d e f)
変数 x と y に格納されているリストを append! で連結します。このとき、変数 x の値は書き換えられることに注意してください。
関数 reverse はリストの要素を逆順にした新しいリストを生成して返します。ここで、リストを破壊的に修正する関数 reverse! を考えてみましょう。Gauche (srfi-1) には reverse! が用意されていますが、私たちでもプログラムすることができます。次の図を見てください。
A B C
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ls─→│ａ│・┼─→│ｂ│・┼─→│ｃ│・┼─→ ()
└─┴─┘ └─┴─┘ └─┴─┘
↑
変数r ─→ () ─┘書き換える
(1) セル A の CDR 部を書き換える
B C
┌─┬─┐ ┌─┬─┐
変数ls─→│ｂ│・┼─→│ｃ│・┼─→ ()
└─┴─┘ └─┴─┘
↑
A──┘書き換える
┌─┬─┐
変数r ─→│ａ│・┼─→ ()
└─┴─┘
(2) セル B の CDR 部を書き換える
C
┌─┬─┐
変数ls─→│ｃ│・┼─→ ()
└─┴─┘
↑
B──┘書き換える
┌─┬─┐ ┌─┬─┐
変数r ─→│ｂ│・┼─→│ａ│・┼─→ ()
└─┴─┘ └─┴─┘
(3) セル C の CDR 部を書き換える
変数ls ─→ ()
C B A
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数r ─→│ｃ│・┼─→│ｂ│・┼─→│ａ│・┼─→ ()
└─┴─┘ └─┴─┘ └─┴─┘
(4) 完成
図 : reverse! の動作
変数 ls に格納されたリストを逆順にします。このとき、変数 r に逆順のリストを保持します。考え方は簡単で、リストの先頭から要素を順番に取り出して、変数 r のリストに追加していくところは reverse と同じです。この操作をセルをつなぎかえることで行っているのが reverse! です。つまり、セルごと要素を移動しているのです。
これをプログラムすると次のようになります。
リスト : reverse! (破壊的操作)
(define (my-reverse! ls)
(let loop ((ls ls) (r '()))
(if (null? ls)
r
(let ((x (cdr ls)))
(set-cdr! ls r)
(loop x ls)))))
関数名は my-reverse! としました。引数 ls のリストを破壊的な操作で要素を逆順にします。変数 r に逆順のリストを保持します。ls が空リストの場合は r を返します。そうでなければ、ls の先頭のセルを r に追加します。
まず、2 番目のセルを変数 x にセットします。それから、先頭セルの CDR 部を r に書き換えます。これで、r の先頭にセルを移動することができます。あとは、loop を再帰呼び出しするとき、第 1 引数に x を、第 2 引数に ls を渡します。ls の先頭のセルが逆順のリストの先頭になっていることに注意してください。
それでは簡単な例を示しましょう。
gosh> (define a (list 1 2 3 4)) a gosh> a (1 2 3 4) gosh> (define b (my-reverse! a)) b gosh> b (4 3 2 1) gosh> a (1)
my-reverse! の返り値を代入した変数 b の値は逆順のリストになっています。ところが、変数 a の値は逆順のリストになっていません。my-reverse! は変数 a のリストを破壊的に修正しますが、変数 a の値が逆順のリストになるわけではありません。これは srfi-1 の関数 reverse! も同じ動作になります。ご注意くださいませ。
それでは簡単な例題として、リストを使って「キュー (queue) 」という基本的なデータ構造を実装してみましょう。なお、Gauche にはキューを操作するライブラリ (util.queue) が用意されていますが、勉強のため実際にプログラムを作ってみましょう。
キューは「待ち行列」といわれるデータ構造です。たとえば、チケットを買う場合窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out) 」とも呼ばれます。
先頭 最後尾
---------------------------
<= a b c d e . . . z <=
---------------------------
先頭 最後尾
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
queue ─→│・│・┼─→│・│・┼─→│・│・┼・・・→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
ａ ｂ ｃ ｚ
図 : キューの構造
キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。
たとえば、データの追加に append を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると実行時間がかかるようになります。そこで、append の代わりに append! を使うことを考えてみます。この場合、リストのコピーは回避できますが、最後尾のセルは先頭から順番にセルをたどっていかないと到達できないので、データが多くなるとやっぱり時間がかかってしまいます。
そこで、最後尾のセルを格納する変数を用意することにします。
先頭 最後尾
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
front ─→│ａ│・┼─→│ｂ│・┼─→│ｃ│／│
└─┴─┘ └─┴─┘ └─┴─┘
↑
rear ─────────────────┘
図 : キューの構造（改良版）
上図に示すように、リストを保持する変数 front のほかに、最後尾のセルを格納する変数 rear を用意します。このようなデータ構造を作成する場合、Gauche ではオブジェクトシステムを使う、オブジェクトシステムがない Scheme では「構造体」を使うところですが、まだ説明していないので、今回はクロージャを使ってプログラムを作ることにします。
キューを操作するプログラムは次のようになります。
リスト : リストによるキューの実装
(define (make-queue)
(let ((front '()) (rear '()))
; キューにデータを追加する
(define (enqueue! item)
(let ((new-cell (list item)))
(if (null? front)
; キューは空
(set! front new-cell)
; 最後尾のセルを書き換える
(set-cdr! rear new-cell))
(set! rear new-cell)))
; キューからデータを取り出す
(define (dequeue!)
(if (null? front)
#f
(let ((item (car front)))
(set! front (cdr front))
(if (null? front)
; キューは空になった
(set! rear '()))
item)))
:
(lambda (x . args)
(cond ((eq? x 'enqueue!)
(enqueue! (car args)))
((eq? x 'dequeue!)
(dequeue!))
((eq? x 'empty?)
(null? front))
(else #f)))))
関数 make-queue は空のキューを生成し、その操作を行うクロージャを返します。let で局所変数 front と rear を定義して空リストに初期化します。define と同様に、let の先頭部分でも内部関数を定義することができます。
内部関数 enqueue! はキューにデータを入れる処理を行います。最初に、item をリストに格納して new-cell にセットします。変数 front が空リストの場合、キューは空なので、front に new-cell をセットします。キューにデータがある場合は、最後尾のセル rear の CDR 部を set-cdr! で書き換えて new-cell を連結します。最後に new-cell を rear にセットして最後尾のセルを更新します。
キューからデータを取り出す内部関数が dequeue! です。front が空リストの場合、キューにデータはないので #f を返します。キューにデータがある場合は、先頭の要素を取り出して変数 item にセットします。それから、front の先頭のセルを削除します。この操作でキューが空になった場合は、変数 rear に空リストをセットします。これでキューを空にすることができます。
最後にラムダ式でクロージャを返します。enqueue! と dequeue! で引数の個数が違うので、ラムダ式は可変個の引数を受け取るように定義します。
Scheme の場合、ラムダ式の仮引数は次に示す 3 通りのパターンがあります。
1 は今までの関数呼び出しと同じ形式で、3 個の仮引数 a, b, c があります。この場合、実引数も 3 個必要になります。2 はドットリストで仮引数を表していて、仮引数 a, b, c は 1 と同じですが、引数 args には残りの引数がリストに格納されて渡されます。つまり、3 個以上の引数を受け取ることができます。3 のように変数 args だけの場合、与えられた引数すべてがリストに格納されて args に渡されます。引数がない場合、args は空リストになります。つまり、0 個以上の引数を受け取る関数になります。
簡単な例を示しましょう。
gosh> ((lambda (a b c . args) (list a b c args)) 1 2 3) (1 2 3 ()) gosh> ((lambda (a b c . args) (list a b c args)) 1 2 3 4 5 6) (1 2 3 (4 5 6)) gosh> ((lambda args (list args))) (()) gosh> ((lambda args (list args)) 1 2 3) ((1 2 3))
このように、可変個の引数を受け取る関数を定義することができます。
ラムダ式 (lambda (x . args) ...) は、引数 x に呼び出す内部関数の種類を指定し、残りの引数は args に渡されます。x がシンボル enqueue! の場合は、内部関数 enqueue! を呼び出します。このとき、args の先頭の要素をキューに追加するデータとして渡します。dequeue! の場合は内部関数 dequeue! を呼び出します。empty? はキューが空の場合は #t を返す述語とします。この処理は (null? front) だけなので、ラムダ式の中で処理します。
これでプログラムは完成です。それでは実行してみましょう。
gosh> (define q (make-queue)) q gosh> (for-each (lambda (x) (q 'enqueue! x)) '(1 2 3 4 5)) #<undef#> gosh> (while (not (q 'empty)) (format #t "~D~%" (q 'dequeue!))) 1 2 3 4 5 #<undef> gosh> (q 'empty) #t
正常に動作していますね。
リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list) 」といいます。次の図を見てください。
CDR 部を直接 CELL A に書き換える
└──────┐
CELL A ↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
┌───────────────┐
↓ │
┌─┬─┐ ┌─┬─┐ ┌─┬┼┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│・│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
図 : 循環リスト
リスト (a b c) は空リストで終端されています。このリストで、最後尾のセルの CDR 部を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。それでは、実際に循環リストを作ってみましょう。
gosh> (define z (list 'a 'b 'c)) z gosh> (set-cdr! (cddr z) z) #<undef> gosh> z #0=(a b c . #0#) gosh> (car (cdddr z)) a
(cddr z) で最後尾のセルを取り出して、set-cdr! で CDR 部を先頭のセルに書き換えます。Gauche の場合、循環リストは #0=(a b c . #0#) と表示されます。循環リストに終わりはないので、最後の例のように cdr を 3 回適用すると先頭の要素 a が表示されます。
Common Lisp や Scheme (srfi-38) では、#n= により Scheme (Lisp) データにラベルを付けることができます。n には整数値を指定し、#n# でそのデータを参照することができます。#0=(a b c . #0#) の場合、#0= で先頭のセルにラベルがつけられ、最後尾のセルの CDR 部で先頭のセルを #0# で参照しています。これで循環リストを表すことができます。
また、#n= と #n# はプログラムで使うことができます。たとえば、(define z '#0=(a b c . #0#)) とすれば、循環リストを生成して変数 z にセットすることができます。ほかの例も示しましょう。
gosh> (define a '("abc" "abc"))
a
gosh> (define b '(#0="abc" #0#))
b
gosh> (eq? (car a) (cadr a))
#f
gosh> (eq? (car b) (cadr b))
#t
Scheme (Lisp) の場合、リスト ("abc" "abc") の 2 つの文字列 "abc" は別々のデータとして生成されるのが普通です。したがって、2 つの文字列を eq? で比較すると #f になります。ところが (#0="abc" #0#) とすると、最初の文字列にラベルが付けられて次の要素でその文字列を参照しているので、リストは同一の文字列データを格納することになります。よって、リストの第 1 要素と第 2 要素を eq? で比較すると #t になるのです。
それから、循環リストを display で表示しようとすると、(a b c a b c a b c ... のように人が手動で中断しない限り止まらなくなります。ご注意くださいませ。
なお、ライブラリ srfi-1 には循環リストを生成する関数 circular-list が用意されています。実際に循環リストを作る場合は、この関数を使用するとよいでしょう。
循環リストのチェックは「うさぎとかめ」のアルゴリズムを使うと簡単です。「うさぎ」と「かめ」はリストをたどる変数として定義します。うさぎは cdr を 2 回適用して進みますが、かめは cdr を 1 回適用して進みます。うさぎがリストの終端に到達すれば、リストは循環していないことがわかります。うさぎがかめに追いつけば、リストは循環していると判断できます。プログラムは次のようになります。
リスト : 循環リストのチェック
(define (my-circular-list? ls)
(if (or (null? ls) (null? (cdr ls)))
#f
(let loop ((fast (cddr ls)) (slow (cdr ls)))
(cond ((null? fast) #f)
((eq? fast slow) #t)
(else
(loop (cddr fast) (cdr slow)))))))
srfi-1 には述語 circular-list? が定義されているので、名前は my-circular-list? としました。変数 fast が「うさぎ」で slow が「かめ」を表します。fast は cddr で、slow は cdr で進みます。fast が終端に到達すれば循環リストではありません。#f を返します。うさぎがかめに追いつくと fast と slow の値は同じセルになるので、(eq? fast slow) の評価結果は真になります。この場合は #t を返します。あとは、リストをたどってチェックを続行します。
それでは実際に試してみましょう。
gosh> (my-circular-list? '#0=(a b c . #0#)) #t gosh> (my-circular-list? '(a b c d)) #f gosh> (my-circular-list? '()) #f
正常に動作していますね。
簡単な例題として、今度は循環リストを使って「キュー (queue) 」を実装してみましょう。循環リストの場合、最後尾のセルを参照する変数 rear を用意するだけでキューを実現することができます。下図を見てください。
rear ─→ None
(1) キューが空の状態
rear ───┐
↓
┌─┬─┐
┌─→│・│・┼─┐
│ └┼┴─┘ │
│ ↓ │
│ data1 │
│ │
└────────┘
(2) キューにデータが一つある場合
rear ─────────────────────┐
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
┌─→│・│・┼→│・│・┼→│・│・┼→│・│・┼─┐
│ └┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘ │
│ ↓ ↓ ↓ ↓ │
│ data1 data2 data3 data4 │
│ │
└──────────────────────────┘
(3) キューに複数のデータがある場合
図 : 循環リストによるキューの構造
循環リストの場合、最後尾のセルの次のセルが先頭になります。(3) を見てください。循環リストの場合、rear が参照する最後尾のセルの CDR 部は空リストではありません。CDR 部が参照するセルがキューの先頭になるのです。データが一つしかない場合、(2) のように rear が参照するセルの CDR 部は自分自身を参照しています。つまり、このセルが先頭であり最後尾でもあるわけです。キューにデータがない場合、rear の値は (1) のように空リストとします。
それではプログラムを作りましょう。次のリストを見てください。
リスト : 循環リストによるキューの実装
(define (make-queue)
(let ((rear '()))
; キューへデータを追加
(define (enqueue! item)
(let ((new-cell (list item)))
(cond ((null? rear)
; キューは空
(set-cdr! new-cell new-cell))
(else
(set-cdr! new-cell (cdr rear))
(set-cdr! rear new-cell)))
(set! rear new-cell)))
; キューからデータを取り出す
(define (dequeue!)
(if (null? rear)
#f
(let ((front (cdr rear)))
(if (eq? front rear)
(set! rear '())
(set-cdr! rear (cdr front)))
(car front))))
;
(lambda (x . args)
(cond ((eq? x 'enqueue!)
(enqueue! (car args)))
((eq? x 'dequeue!)
(dequeue!))
((eq? x 'empty?)
(null? rear))
(else #f)))))
関数 make-queue は空のキューを生成し、その操作を行うクロージャを返します。let で局所変数 rear を定義して空リストに初期化します。次に、内部関数 enqueue! を定義します。最初に、item をリストに格納して new-cell にセットします。変数 rear が空リストの場合、キューは空なので new-cell の CDR 部を自分自身に書き換えてから、最後で rear にセットします。
キューにデータがある場合は、rear の後ろに new-cell を連結します。まず、new-cell の CDR 部を (cdr rear) に書き換えます。これで new-cell の後ろに先頭のセルが接続されます。それから、rear の CDR 部を new-cell に書き換えます。これで、rear と先頭のセルの間に new-cell を挿入することができます。最後に new-cell を rear にセットします。
次に dequeue! を定義します。rear が空リストの場合、キューにデータはないので #f を返します。キューにデータがある場合は、先頭のセル (cdr rear) を変数 front にセットします。front と rear が eq? で等しい場合、最後のデータを取り出してキューは空になります。この場合、rear に空リストをセットします。そうでなければ、rear の CDR 部を (cdr front) に書き換えて、front のセルを循環リストから外します。最後に front の要素 (car front) を返します。
これでプログラムは完成です。それでは実行してみましょう。
gosh> (define q (make-queue)) q gosh> (for-each (lambda (x) (q 'enqueue! x)) '(1 2 3 4 5)) #<undef#> gosh> (while (not (q 'empty)) (format #t "~D~%" (q 'dequeue!))) 1 2 3 4 5 #<undef> gosh> (q 'empty) #t
正常に動作していますね。
今回はここまでです。簡単に復習しておきましょう。
次回は「二分木 (binary tree) 」というプログラムでよく用いられるデータ構造を紹介します。