リスト と対

リスト

(list)

^{とは 、}(yumiko mayuko hiroko noriko) のように 、括弧で囲まれたいく つのデータ

(

記号のみとは限りません

)

のならびをいいます。リストの構成要素がまたリス トであっても構いません。リストの例を以下に示します

:

() (a)

(NISHIDA HIKARU) (1 a 2 b)

((pi 3.1415) (e 2.71828))

(a (ba bb) (ca (cba cbb) cc) d)

3この規則に従うと-Aも記号となります。

最初の行の () は空リスト

(empty list)

^という、「何もないリスト 」を表すデータです。

空リストは、リストの終りを表すのにも使います。 空リストをプログラム中に書くときは、

引用符を忘れずに '()と書いて下さい。空リストを画面に表示すれば () となるだけです が 、プログラム入力のときは '()とします⁴。

与えられたデータが空リストかど うかを判定するには、手続きnull?を使います。

} (null? ^h変数ⁱ)

|

^{h変数iの値が空リストなら真#tを、そうでなければ偽 #fを返します。}

> (null? '(yumiko mayuko))

#f

> (null? '(yumiko))

#f

> (null? '())

#t

> (null? 'miho)

#f

リストの長さには制限はなく、好きな長さのリストを作ることができます⁵。数を値とし て持っていた変数に、記号を代入してこれを新しい値にすることも可能です。このように、

Scheme

ではデータの取り扱いにおいて非常に柔軟性があります。

C

^や

Pascal

^や

Fortran

などの言語ですと、変数はどのデータ型のものであるかをあらかじめ宣言しておき、宣言 された型のみの代入しか許していません⁶。

リストは、実は対

(pair)

と呼ばれる、より基本的なデータを組み合わせて作られます。対 の説明をする前に、与えられたリストに含まれている構成要素を調べる方法を説明します。

リストは、要素がいくつかならんだものでした。最初の要素を返す手続きが carで、最 初の要素を取り除いたリストを返す手続きが cdrです⁷。なお、carは「カー」と、cdrは

「クダー」と発音します。

4というのも、単に()とすると「手続き名を書き忘れた、手続き呼び出し 」とみなされるからです。

(Scheme

処理系によっては()という書き方を許しています。しかしこれは

Scheme

の言語仕様では許されていない 書式なので、そのような書き方はしないで下さい。

)

5もっとも主記憶装置の容量には限りがありますので、その範囲内で、という意味です。

6これにも長短があります。

Scheme

のように変数の宣言がないと、プログラムを作るときに変数名のつづ りを間違っても、実際に走らせてみなければそれに気がつきません。

Pascal

などの変数宣言をする言語です と、プログラムを機械語へ翻訳するとき

(

^{プログラム作成時}

)

^{に変数名のチェック}

(

^{つづりやデータ型}

)

^をおこ

ない、実行時にはそれをおこないません。もし実行時に型エラー

(

記号と数を加えようとしてしまう間違い など

)

が起き、プログラムが中断されては重大な事態になってしまうことがあります。

(

^{とくに、原子炉の制}

御や集中治療室の制御などでは人命に関わる事態です。

)

そのような場合で使われるプログラムは 、前もっ て変数の名前や型をチェックする必要があります。

7

1950

^{年台後半のころ、}

IBM

^社の

IBM 7090

という計算機で 、世界で最初の

Lisp (Scheme

^{ご 先祖にあ}

たる言語

)

の処理系が作られたことに由来しています。

IBM 7090

の機械語命令にはアドレス

(address)

^部と

デクリメント

(decrement)

^{部があって、}

car

^は

Contents of Address part of Register

^の、

cdr

^は

Contents of Decrement part of Register

^{の略です。いまや}

IBM 7090

は死に絶えてしまっているのに、

car

^や

cdr

^はこ

んにちでも使われ続けています。

> (define idols '(hikaru miho hiroko noriko))

#<unspecified>

> (car idols) hikaru

> (cdr idols)

(miho hiroko noriko))

carではリストの最初の要素しか取り出せませんが 、carと cdr を組合せることで、

2

番めの要素や

3

番めの要素も取り出すことができます。

> (car (cdr idols)) miho

> (car (cdr (cdr idols))) hiroko

> (car (cdr (cdr (cdr idols)))) noriko

3

^番目や

4

番目の要素を取り出すのに carや cdrを何度も書くのはめんど くさいので、

carと cdrを組み合わせた手続きが用意されています。たとえば (cadr

S

^{)は (car (cdr}

S

^{)) と同じで 、(cadar}

S

^{) は} (car (cdr (car

S

⁾⁾⁾と同じです。このほかにも carと cdrを

4

つまで組み合わせた手続きが用意されています。

(

^{たとえば 、cadr}

,

^caddr

,

^cadddr

など 。

)

では、上の例と同じことをやってみましょう。

> (cadr idols) mami

> (caddr idols) hiroko

> (cadddr idols) noriko

前で説明したように、リストは

Scheme

の基本的なデータ型ではありません。リストは

対

(pair)

と呼ばれる基本データ型を組み合わせたものです。図

3.1(a)

^{のように、対は}

2

^つ

の

Scheme

データを収めるハコのようなものです。

(

^図

3.1(c)

^には、

3

^{つの対があります。}

)

対は cons という手続きで作られます⁸。手続き cons は 、

2

つの引数を持ちます。式

(cons

a b

⁾ を評価するときには、まず新しいハコ

(

^対

)

が用意され 、ハコの前の部分に

a

(

^の評価値

)

を、ハコの後ろの部分に

b (

^の評価値

)

を入れます。そうしてこのハコが、(cons

8consは

construct (

英語で「構成する」、の意

)

にちなんで付けられた名前で、リストを「構成する」の でこの名前がつけられました。

3

. .

. .

..

. .

. .

. .

. .

. .

. .

. .

. .

..

..

. .

..

..

. .

. .

..

. .

. .

. .

. ..

..

. ..

..

..

..

... . . . . . . . . . . . . . . . . . .

.

. .

. .

.

..

. .

.

. .

.

. .

. .

. . .. . . . . . . . . . . . .. . . .

. .

..

.

. .

. .

.

. .

..

.

. .

. .

.

. .

. .

. .

.

. .

.

. .

. .

.

. .

. .

. .

.

. .

.

. .

. .

.

. .

. .

. .

.

. .

.

. .

. .

. .

.

. .

. .

.

..

.

. .

. .

. . .

..

. .

.

. .

. .

..

.

. .

. .

. . . . . . . . . . . . . . . . . . . . .

..

. .

. .

..

..

. .

..

..

. .

..

..

. .

. .

. .

. .

. .

..

. .

. .

.. ..

...

. .

. .

...

. .

. ..

... . . . . . . . . . . . . . . . . . .

...... . .....

......... . . . . . . . . . . . . . . . . .

.

. .

. .

.

. .

..

.

. .

.

..

. .

. . . . .. . . . . .. . . . . . .. .

. .

. .

.

..

. .

.

. .

. .

.

. .

. .

.

. .

. .

. .

.

. .

.

. .

. .

.

. .

. .

..

.

. .

.

. .

. .

.

. .

..

. .

.

. .

.

. .

..

. .

.

. .

. .

.

. .

.

..

. .

. . .

. .

. .

.

. .

. .

..

.

. .

..

. . . . . . . . . . . . . . . . . . . . .

. .

. .

.

..

. .

.

. .

.

. .

. .

. . . . .. . . . . .. . . . . . .. . .

..

. .

. .

. .

. .

. .

..

. .

. .

..

. .

. .

..

. .

. .

..

. .

. .

..

. . ..

. ..

..

..

...

. .

...

. . . . . . . . . . . . . . . . . . . . .

(c)

(cons 1 (cons 2 3))の評価結果

(b)

^{(cons 2 3)の評価結果}

(a)

^対

1 2 3

2

図

3.1:

^対

a b

^{) の評価値}

(

^実行結果

)

として返されます。この理由のため、対の前の部分は

car

^部、

後ろの部分は

cdr

^部と、それぞれ呼ばれます。

以上のことをまとめると次のようになります。

} (car ^h対ⁱ)

|

^{h対i の}

car

^{部を取り出します。}

} (cdr ^h対ⁱ)

|

^{h対i の}

cdr

^{部を取り出します。}

対は (

a

^.

b

^{) のように 、要素を . で区切り、 括弧 ( と )} で囲むことで表されます。

たとえば (cons 1 2)を評価すると、対(1 . 2)が作られます。

(

^図

3.1(b)

^{を参照してく}

ださい。

)

^{まんなかの点.は、 対を構成する}

2

つの要素を区切るためのもので、小数点で はありません。

(

^. の前後に空白文字がありますので、注意深く見れば区別がつきます。

)

ではもう少し複雑な例を見てみましょう。式 (cons 1 (cons 2 3)) を評価すると、上 で学んだことから考えると(1 . (2 . 3)) が得れることがわかります。このように . を使った書き方を、ド ット 記法

(dotted notation)

^{と呼んでいます。}

普通はド ット記法(a . (b . ())) のように書かずに、(a b)と書きます。より一般 的にいえば 、(a1 . (a2 . (an . ()) )) を(a1 a2 an)と書き表します。こ のような書き方を リスト 記法

(list notation)

^{と呼んでいます。}

式 (cons 1 (cons 2 3))を評価してみましょう。

()

. .....

...... .........

. . . . . . . . . . . . . . . . .

.

. .

. .

.

. .

..

.

. .

.

. .

..

. . . . . . . . . . . . .. . . . . . . .

. .

. .

.

. .

..

.

. .

.

. .

..

. . . . . . . . . . . . .. . . . . . . .

. .

. .

..

. .

. .

..

. .

. .

..

. .

. .

..

. .

. .

..

. .

. .

..

. .

. . . .

. ..

..

. .

. ..

..

...

. . . . . . . . . . . . . . . . . . . . .

. .....

...... .........

. . . . . . . . . . . . . . . . .

.

. .

. .

.

. .

..

.

. .

.

. .

..

. . . . . . . . . . . . .. . . . . . .

b

a c

図

3.2:

^{リスト(a b c)}

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

結果は(1 . (2 . 3))ではなく、(1 2 . 3)と表示されました。ほとんどすべての

Scheme

処理系では、ド ット記法でなく改良リスト記法を使ってデータを表示します⁹。と

いうのも、ド ット記法を使うと、長いリストの時は括弧をたくさん表示しないといけない からです。

リスト

(list)

^とは対が

cdr

部で連なったもので、しかも最後の対の

cdr

^{部が空リストで}

あるものをいいます。図

3.2

のように 、最後の対の

cdr

部が空リストでないときはリスト とは呼びません。

与えられたデータが対かど うか 、あるいはリストかど うかを判定するために 、手続き

pair? と手続きlist? が用意されています。

} (pair? ^hデータⁱ)

|

^{hデータiが対なら真#t を、そうでなければ偽#f を返します。}

} (list? ^hデータⁱ)

|

^{hデータiがリストなら真#t を、そうでなければ偽 #f を返します。}

手続きpair? は、与えられたデータがハコかど うか調べるだけです。

(

^ハコの

car

^部や

cdr

部がどのような値を持っているかは、一切調べません。

)

^{いっぽう手続きlist? は、ま}

ず与えられたデータがハコかど うか調べます。次にそのハコの

cdr

^{部もさらにハコになっ}

ているかを繰り返し調べます。最後に空リストにたどり着けばそのデータはリストである、

と判定します。これが pair? と list? の違いです。

> (pair? '(a b))

#t

> (pair? '())

|

^{空リストは対ではない}

!

9改良リスト記法とは、できる限りリスト記法を使うのですが 、リスト記法が使えない時のみド ット記法 を使う方法です。この方法では、(a1 . (a2 . (am (an . ())) ))は、(a1 a2 am . an)と 表記されます。

#f

> (pair? '(1 . 2))

#t

> (list? '(a b c))

#t

> (list? '())

#t

> (list? '(1 . 2))

#f

> (list? '(0 1 . 2))

#f

list?

,

^pair?

,

^null? の関係を、以下に例示します。

データ

'() (pooh) (pooh piglet owl) (kanga . roo)

list? #t #t #t #f

pair? #f #t #t #t

null? #t #f #f #f

ドキュメント内 Copy Free \Scheme " Copy Free \Scheme " 2 (2a) (2b) (2c) 3 (3a) (The Internet) (3b) (6a) (6b) (6c) (6d) Scheme (ページ 40-45)