3. リストを作ろう¶
始めに¶
Scheme は Lisp 語族なので, リストの操作が上手. Scheme を使いこなすために, リストについてしっかり理解しておく必要がある.
リストは後で出てくる再帰関数, 高階関数で重要な役割を果たしている.
ここでは基本的な関数は:
cons
car
cdr
list
quote
コンスセル¶
まず, リストの構成要素であるコンスセルについて説明する.
コンスセルとはアドレスを２つ格納したメモリ領域である. コンスセルは cons という関数で作ることができる.
guile 処理系に (cons 1 2) と入力してみたら:
guile> (cons 1 2)
(1 . 2)
(1 . 2) と表示される.
cons は 図 1 に示すようにアドレスが２つ分入るメモリ領域を確保し, 片方に 1 へのアドレスを, もう片方に 2 へのアドレスを入れる.
1 へのアドレスが入っている方を car 部,
2 へのアドレスが入っている方を cdr 部と呼ぶ:
car = ContentsoftheAddressoftheRegister
cdr = ContentsoftheDecrementpartoftheRegister
cons は構成するという意味の英単語 construct の略である.
コンスセルは念珠つなぎにすることができる:
guile> (cons 3 (cons 1 2))
(3 1 . 2)
結果 (3 1 . 2) は ( 3 . (1 . 2)) の省略形である. このとき, メモリは図 2 のようになっている.
また, 違う種類のデータを組み合わせることができる:
guile> (cons #\F (cons "feifei" 28))
(#\F "feifei" . 28)
guile> (cons (cons 0 1) (cons 2 3))
((0 . 1) 2 . 3)
このようなことができるのは, Scheme が全てのデータをアドレスで管理しているから.
リスト¶
一番最後のコンスセルの cdr 部が ‘() になった一連のコンスセルをリストと呼ぶ. ‘() は空リストと呼ばれ, これもリストに含める. コンスセルが１つの場合でも, その cdr が ‘() ならリストである.
リスト (1 2 3) は図 3 のようなメモリ構造になっている.
実はリストは再帰的に以下のように定義される:
1. '() はリストである
2. ls をリストとし, obj を任意のオブジェクトとすると, (cons obj ls) はリストである.
このように, リストは再帰的に定義されているデータ構造なので, 後で述べる再帰関数や高階関数にしばしば使われるデータ構造になる.
練習問題 1¶
guile 処理系が次のように表示するデータ構造を cons で作ってください.
P1. (“hi” . “everybody”):
guile> (cons "hi" "everybody")
("hi" . "everybody")
P2. (0):
guile> (cons 0 '())
(0)
P3. (1 10 . 100):
guile> (cons 1 (cons 10 100))
(1 10 . 100)
P4. (1 10 100):
guile> (cons 1 (cons 10 (cons 100 '())))
(1 10 100)
P5. (#I “saw” 3 “girls”):
guile> (cons #\I (cons "saw" (cons 3 (cons "girls" '()))))
(#\I "saw" 3 "girls")
P6 (“Sum of” (1 2 3 4) “is” 10):
guile> (cons "Sum of" (cons (cons 1 (cons 2 (cons 3 (cons 4 '())))) (cons "is" (cons 10 '()))))
("Sum of" (1 2 3 4) "is" 10)
quote¶
Scheme では, 値が括弧の内側から外側に向けて評価が行われ, 一番外側の括弧が評価した値がその式の値として返ってくるという計算法を取っているため, トークン (プログラム言語における意味を持つ最小単位, ほとんど単語と同じ意味) は常に評価される危険にさらされる.
そこで, シンボルやリストなど, 評価されると自分自身にならないデータそのものをプログラムに与えるときは quote という命令を使う.
例えば, (+ 2 3) は評価されると 5 になるが, (quote (+ 2 3)) とすれば (+ 2 3) そのものをプログラムに与えることができる. quote はしばしば使われるので ‘ で代用される. つまり, ‘(+ 2 3) は (+ 2 3) というリストを表す.
注意:
quote はリストだけでなく, シンボルの評価も止める. 例えば '+ は + というシンボルそのものを指す.
実は ‘() は空リスト () を quote したものである. 従って, 入力するときには ‘() を使うが, 処理系から空リストが表示されるときは () が使われる.
特殊形式¶
Scheme は括弧の中身を全て評価して括弧の外に値を返す関数と, それ以外の働きをする特殊形式からなっている.
特殊形式には今見た quote のほかに lambda, define, if, set! などがある.
関数 car と cdr¶
コンスセルの car 部を返す関数を car, cdr 部を返す関数を cdr という.
cdr が返す値がリストなどのコンスセルの列なら, その列の (car 部の) 値全体が表示される. 最後のコンスセルの cdr 部が ‘() でなければ . で区切って, その値も表示される:
guile> (car '(1 2 3 4))
1
guile> (cdr '(1 2 3 4))
(2 3 4)
guile> (cddr '(1 2 3 4))
(3 4)
guile> (cdddr '(1 2 3 4))
(4)
guile> (cddddr '(1 2 3 4))
()
練習問題 2¶
次の値を求めてください:
guile> (car '(0))
0
guile> (cdr '(0))
()
guile> (car '((1 2 3) (4 5 6)))
(1 2 3)
guile> (cdr '((1 2 3) (4 5 6)))
((4 5 6))
guile> (cddr '((1 2 3) (4 5 6)))
()
guile> (cdr '(1 2 3 . 4))
(2 3 . 4)
guile> (cddr '(1 2 3 . 4))
(3 . 4)
guile> (cdddr '(1 2 3 . 4))
4
guile> (cons 1 '())
(1)
guile> (cons 2 (cons 1 '()))
(2 1)
guile> (cons 3 (cons 2 (cons 1 '())))
(3 2 1)
guile> (cdr (cons 3 (cons 2 (cons 1 '()))))
(2 1)
関数 list¶
複数の要素からなるリストを作るときは関数 list を使うほうが便利である.
list は任意個の引数をとり, それらからなるリストを返す:
guile> (list)
()
guile> (list 1)
(1)
guile> (car (list 1))
1
guile> (cdr (list 1))
()
guile> (list 1 2 3 4 5 6)
(1 2 3 4 5 6)
guile> (list 0)
(0)
guile> (list '(1 2) '(3 4) '(5 6))
((1 2) (3 4) (5 6))
guile> (car (list '(1 2) '(3 4) '(5 6)))
(1 2)
guile> (car (car (list '(1 2) '(3 4) '(5 6))))
1
