3. リストを作ろう

1. 初めに

Scheme は Lisp 語族なので、リストの操作が上手です。 Scheme を使いこなすためにもリストについてはしっかり理解しておく必要があります。リストは後で出てくる再帰関数、高階関数で重要な役割を果たします。

ここでは基本的な関数である cons, car, cdr, list および quote について説明します。

2. コンスセルとリスト

2.1. コンスセル

まず、リストの構成要素であるコンスセルについて説明します。コンスセルとはアドレスを２つ格納したメモリー領域です。コンスセルは cons という関数でつくることができます。処理系に (cons 1 2) と入力してみてください。

> (cons 1 2)
(1 . 2)

(1 . 2) と表示されます。 cons は図１に示すようにアドレスが 2 つ分入るメモリー領域を確保し、片方に 1 へのアドレスを、もう片方に 2 へのアドレスを入れます。 1 へのアドレスが入っている方を car 部、 2 へのアドレスが入っている方を cdr 部と呼びます。 car は Contents of the Address part of the Register の略で、一方、 cdr は Contents of the Decrement part of the Register の略です。これは、Lisp が実装された初期のハードウェアのメモリーの部位の名前です。このことからコンスセルの実態がメモリー領域であることが伺えます。ちなみに、cons は構成するという意味の英単語 construct の略です。

図1: コンスセル

コンスセルは数珠つなぎにすることができます。

> (cons 3 (cons 1 2))
(3 1 . 2)

(3 1 . 2) というのは (3 . (1 . 2)) の省略形です。このとき、メモリーは図２の様になっています。

図2: 連なったコンスセル

また、違う種類のデータを組み合わせることもできますし、入れ子にすることもできます。

> (cons #\a (cons 3 "hello"))
(#\a 3 . "hello")

> (cons (cons 0 1) (cons 2 3))
((0 . 1) 2 . 3)

このようなことができるのは、Scheme が全てのデータをアドレスで管理しているからです。ちなみに #\c は c という文字を表します。例えば #\a は a という文字を表します。

2.2. リスト

一番最後のコンスセルの cdr 部が '() になった一連のコンスセルをリストと呼びます。 '() は空リストと呼ばれ、これもリストに含めます。コンスセルが1つの場合でも、その cdr が '() ならリストです。リスト (1 2 3) は図3のようなメモリー構造になっています。

図3: リスト

実はリストは再帰的に以下の様に定義されます。

'() はリストである。
ls をリストとし、obj を任意のオブジェクトとすると、 (cons obj ls) はリストである。

このように、リストは再帰的に定義されているデータ構造なので後で述べる再帰関数や高階関数にしばしば使われるデータ構造になります。

2.3. アトム

コンスセルを使っていないデータを atom といいます。数値、文字、文字列、ベクトルは atom です。

練習問題 1

処理系が次のように表示するデータ構造を cons で作ってください。

("hi" . "everybody")
(0)
(1 10 . 100)
(1 10 100)
(#\I "saw" 3 "girls")
("Sum of" (1 2 3 4) "is" 10)

3. quote

scheme では、値が括弧の内側から外側に向けて評価が行われ、一番外側の括弧が評価した値がその式の値として返ってくるという計算法を取っているため、トークン(プログラム言語における意味を持つ最小単位、ほとんど単語と同じ意味）は常に評価される危険にさらされます。そこで、シンボルやリストなど、評価されると自分自身にならないデータそのものをプログラムに与えるときは quote という命令を使います。

例えば、(+ 2 3) は評価されると 5 になりますが、(quote (+ 2 3)) とすれば (+ 2 3) そのものをプログラムに与えることができます。quote はしばしば使われるので ' で代用されます。つまり、'(+ 2 3) は (+ 2 3) というリストを表します。リテラル（ソースコードにそのまま書く値）としてリストを作るときは quote を使います。

quote はリストだけでなく、シンボルの評価も止めます。例えば '+ は + というシンボルそのものを指します。

実は '() は空リスト () を quoate したものです。従って、入力するときには '() を使いますが、処理系から空リストが表示されるときは () が使われます。

3.1. 特殊形式

Scheme は括弧の中身を全て評価して括弧の外に値を返す関数と、それ以外の働きをする特殊形式 からなっています。特殊形式には今見た quote のほかに lambda, define, if, set! などがあります。

4. 関数 car と cdr

コンスセルの car 部を返す関数を car、 cdr 部を返す関数を cdr といいます。 cdr が返す値がリストなどのコンスセルの列なら、その列の (car 部の)値全体が表示されます。最後のコンスセルの cdr 部が '() で無ければ . で区切って、その値も表示されます。

> (car '(1 2 3 4))
1

> (cdr '(1 2 3 4))
(2 3 4)

練習問題 2

次の値を求めてください。

(car '(0))
(cdr '(0))
(car '((1 2 3) (4 5 6)))
(cdr '(1 2 3 . 4))
(cdr (cons 3 (cons 2 (cons 1 '()))))

5. 関数 list

複数の要素からなるリストを作るときは関数 list を使うほうが便利です。list は任意個の引数をとり、それらからなるリストを返します。

> (list)
()

> (list 1)
(1)

> (list '(1 2) '(3 4))
((1 2) (3 4))

> (list 0)
(0)

> (list 1 2)
(1 2)

6. 終わりに

今回はリストの基本的な操作について説明しました。ここまでは、ちょっと退屈だったかもしれませんが、次回からはいよいよ本格的にプログラムを作り始めます。まず、エディタでソースコードを編集してそれを処理系で走らせる方法について述べ、それから関数の定義の方法について述べます。

練習問題の解答

練習問題 1

;1
> (cons "hi" "everybody")
("hi" . "everybody")

;2
> (cons 0 '())
(0)

;3
> (cons 1 (cons 10 100))
(1 10 . 100)

;4
> (cons 1 (cons 10 (cons 100 '())))
(1 10 100)

;5
> (cons #\I (cons "saw" (cons 3 (cons "girls" '()))))
(#\I "saw" 3 "girls")

;6
> (cons "Sum of" (cons (cons 1 (cons 2 (cons 3 (cons 4 '())))) (cons "is" (cons 10 '()))))
("Sum of" (1 2 3 4) "is" 10)

練習問題 2

;1
> (car '(0))
0

;2
> (cdr '(0))
()

;3
> (car '((1 2 3) (4 5 6)))
(1 2 3)

;4
> (cdr '(1 2 3 . 4))
(2 3 . 4)

;5
> (cdr (cons 3 (cons 2 (cons 1 '()))))
(2 1)