HOME もうひとつの Scheme 入門 書き込む

3. リストを作ろう


1. 初めに

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

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

2. コンスセルとリスト

2.1. コンスセル

まず、リストの構成要素であるコンスセルについて説明します。 コンスセルとは
アドレス を2つ格納した メモリー 領域です。 コンスセルは cons という関数でつくることが できます。 処理系に (cons 1 2) と入力してみてください。
> (cons 1 2)
(1 . 2)
(1 . 2) と表示されます。 cons は図1に示すように アドレスが 2 つ分入るメモリー領域を確保し、片方に 1 へのアドレスを、もう片方に 2 へのアドレスを入れます。 1 へのアドレスが入っている方を car 部、 2 へのアドレスが入っている方を cdr 部と呼びます。 carContents of the Address part of the Register の略で、一方、 cdrContents 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の様になっています。


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

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

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

> (cons (cons 0 1) (cons 2 3))
((0 . 1) 2 . 3)
このようなことができるのは、Scheme が全てのデータをアドレスで管理しているからです。 ちなみに #\cc という文字を表します。 例えば #\aa という文字を表します。

2.2. リスト

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


図3: リスト

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

  1. '() はリストである。
  2. ls をリストとし、obj を任意のオブジェクトとすると、 (cons obj ls) はリストである。
このように、リストは再帰的に定義されているデータ構造なので 後で述べる再帰関数や高階関数にしばしば使われるデータ構造になります。

2.3. アトム

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

練習問題 1

処理系が次のように表示するデータ構造を cons で作ってください。
  1. ("hi" . "everybody")
  2. (0)
  3. (1 10 . 100)
  4. (1 10 100)
  5. (#\I "saw" 3 "girls")
  6. ("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 部を返す関数を carcdr 部を返す関数を cdr といいます。 cdr が返す値がリストなどのコンスセルの列なら、その列の (car 部の)値全体が表示されます。 最後のコンスセルの cdr 部が '() で無ければ . で区切って、その値も表示されます。
> (car '(1 2 3 4))
1

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

練習問題 2

次の値を求めてください。
  1. (car '(0))
  2. (cdr '(0))
  3. (car '((1 2 3) (4 5 6)))
  4. (cdr '(1 2 3 . 4))
  5. (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)