Lisp 一夜漬け -- 2.リスト

■ Lisp におけるデータ型

	┏ アトム──┬ 数値
	┃           ├ 文字列
	┃           ├ シンボル
	┃           └ nil
	┗ リスト

数値などのように、データ型としてそれ以上分解できないものをアトム(atom「原子」の意)という。 アトムではないものをリストという。 リストはアトムまたはリストを束ねたものである。 リストを分解していくとアトムになる。

アトムの種類は、処理系による。 上に挙げたものはほぼすべての処理系に存在するだろう。

シンボル以外のアトムを評価するとそれ自身が評価結果となる。 前回、「数値345を評価すると345が結果となる」ということを述べた。 文字列も同様で、文字列を評価するとそれ自身が結果となる。 シンボルは変数名や関数名に使われるデータで、 シンボルを評価すると変数として代入された値を返す。

リストにも種類があって、「純リスト」と「純リストでないリスト」に分けられる。

他のプログラミング言語での配列と Lisp でのリストを較べてみよう。 ある一つの型のデータを並べることができる点は共通である。 しかしリストは単一のデータ型だけではなく、どんな型でも並べることができる。

C 言語などの構造体とリストを較べてみる。 色々な型のデータを組み合わせて一つのデータとして扱うことができる点は共通である。 しかしリストでは各要素の型を制限することはないし、動的に構造を変化させることができる。

リストは配列の代わりにもなるし、構造体の代わりにもなるのである。 なお、Common Lisp はリストとは関係なく配列と構造体を言語仕様に含めている。

■ ドット対

リストを作るための最も基本的な関数が cons である。

評価結果は

となる。

括弧の中に、第1引数の評価結果、ピリオド、第2引数の評価結果が書かれている。 この形式のデータのことを「ドット対(dotted pair)」と呼ぶ。 ドット対はアトムではないので、リストである。 ドット対の、ピリオドの左側を「car(かぁ)」部、 右側を「cdr(くだぁ)」部と呼ぶ。 ドット対に入っているデータを取り出す関数が car と cdr である。 car は引数に与えられたドット対の car 部を返し、cdr は cdr 部を返す。

  (car (cons 123 456))  →  123
  (cdr (cons 123 456))  →  456

cons の動作について解説しよう(図1)。 まず2つの引数が評価される。 評価結果はどこかに置いておく。 次に cons セルが生成される。 cons セル は2本の矢印を持っていて、それぞれが car 部、cdr 部に対応している。 そして、car 部の矢印で第1引数の評価結果、cdr 部の矢印で第2引数の評価結果を指す。 この状態で cons セルを評価結果とするのである。 なお、cons セルを図示するときは当然 car 部が左側、cdr 部が右側に描かれる。

図1: cons の動作

ドット対を変数に代入してみよう。

いちいち cons を使うのは面倒なので、ドット対を直接代入したい。

これは間違いである。

Lisp インタプリタは「(123 . 456)」を評価しようとするが、 アトムではないし関数呼び出しでもないのでエラーとなってしまうのである。 そこで、「評価しないでそのまま扱って」と指令する必要がある。 引数を評価しないでそのまま返す quote という特殊形式がある。

を評価すると

である。これを用いれば

と書けるのである。 しかし、これでも冗長であるので、quote には省略記法がある。

は、

と書くことができる。結局、次のようにすればよい。

■ ドット対からリストへ

ドット対はリストの基本ではあるが、データを2つしか持てないように見える。 実際にはドット対の中にドット対を入れることができるので、いくらでもデータを入れることができる。

図2: ドット対で4つのデータ(1)

ドット対を使って4つのデータを格納してみた。 このリストのそれぞれの要素にアクセスするためには、以下のようにすればよい。

    "睦月"  ←  (car (car month))
    "如月"  ←  (cdr (car month))
    "弥生"  ←  (car (cdr month))
    "卯月"  ←  (cdr (cdr month))

この例では各要素は同列に扱いたいとしよう。 しかし上記の構造では欲しい要素ごとにアクセス方法を変えなければならず、不便である。

そこで、次のような構造にする。

図3: ドット対で4つのデータ(2)

各ドット対の car 部に要素を置き、cdr 部に次のドット対を置いている。 最後の要素があるドット対の cdr 部は nil とする。 各要素のアクセス方法は次のようになる。

    "睦月"  ←  (car month2)
    "如月"  ←  (car (cdr month2))
    "弥生"  ←  (car (cdr (cdr month2)))
    "卯月"  ←  (car (cdr (cdr (cdr month2))))

単純に cdr する回数が増えるだけだということがわかるだろう。

この形式のリストのことを「純リスト(pure list)」と呼ぶ。純リストは、

• carすると先頭の要素を返す
• cdrすると先頭の要素を除いた純リストか返る

という性質を持っている。 純リストは簡単に表記することができる。

は、

と同じ意味である。 純リストのこの表記は各データがフラットに置かれているように見えるので、 「"睦月"が1番目の要素で、"如月"が2番目の要素で‥‥」と言いやすい。 もちろん配列とは異なって実際にはドット対によるツリー構造をしているのである。

リストをリストの要素にしても構わないし、純リストでないリストと純リストを混ぜても構わない。

Lisp 中で「リスト」というと純リストのことを指していることが多い。 純リストではないリストよりは純リストのほうが色々な意味で扱いやすくなっているので、 特別な理由がない限りは純リストを使うようにしよう。

■ nil について

前回、nil を「偽を表わす値」として紹介した。 この nil がリストの終端を表わす用途に使われている。 nil はこれ以上分解できないデータであるから、 アトムかどうかを判定する述語関数 atom に渡した結果は真(t)である。

    (atom nil)  →  t

要素が1つしかない純リストに cdr すると何が返るのだろうか。

これは、

と同じ意味であるから、結果は nil である。 「純リストを cdr すると先頭の要素を除いた純リストが返る」より、 nil というのは要素数0の純リストであると言える。 リストかどうかを判定する述語関数 listp に nil を与えた結果は真(t)である。

    (listp nil)  →  t

nil はアトムであり、リストでもある。

C 言語での NULL ポインタが nil に対応しているようなもので、 nil は何も指していないポインタと思ってよい。

■ リストの定義

ここで、リストについてきちんと定義しよう。 Lisp において扱えるすべてのデータを S とする。 S はアトムまたはリストだ。

    S ::= アトム | リスト

広義のリストは、nil もしくは任意のデータのドット対(=consセル)である。

    リスト ::= nil | (S . S)

狭義のリストである純リストは、nil もしくは任意のデータと純リストのドット対である。

    純リスト ::= nil | (S . 純リスト)

■ リストを扱う関数

リストを扱うための基本的な関数についていくつか解説する。 詳しいことは各処理系のマニュアルを見て欲しい。

• (car LIST) (cdr LIST)

先に説明した通り、ドット対の car 部と cdr 部を返す。 引数が純リストならば、car は先頭の要素を取り出すという意味で、 cdr は2番目以降の要素からなるリストを返すという意味である。 cXXr cXXXr cXXXXr (X は a または d) という関数もあり、例えば

(caddr LIST)

は

(car (cdr (cdr LIST)))

と同じである。

• (length LIST)

リストの長さ(=要素数)を整数で返す。

(length '("睦月" "如月" "弥生" "卯月"))

は4である。

(length '("FTP" ("TCP" "UDP") "IP"))

は、3である。このリストは、2番目の要素がリストになっている。 一番外側のリストにとってみれば中にあるリストは一つの要素でしかないわけだ。

• (list E1 E2 E3 ...)

E1 の評価結果を第1要素、E2 の評価結果を第2要素、E3 の評価結果を第3要素‥‥の純リストを返す。

(list (+ 2 3) '(+ 2 3) 5)

の結果は

(5 (+ 2 3) 5)

というリストである。

■ リストを扱うプログラムを作る

まず関数 length の真似をしてみよう。

どうすれば length を実現できるか考える。 BASICやC言語などの手続き型言語でのプログラミング経験がある人が 真っ先に思い付くのは以下のようなアルゴリズムである(C言語のつもりで記述する)。

int my_length( List L ) {
    int i = 0;
    while ( !null( L ) ) { /* nilか? */
        i ++;
        L = cdr( L );
    }
    reutrn i;
}

つまり、リストが空(nil)になるまで繰り返し数えるのである。

Lisp でも do や while などの繰り返しを利用できるのでこのアルゴリズムをそのまま用いることもできる。 が、それは Lisp らしくないプログラムである。 Lisp らしいプログラムでは以下のように考える。

1. 空リストの長さは0である
2. あるリストの長さは、そのリストの先頭要素を取り除いたリストの長さに+1したものである

純リストに cdr すると要素が1つ減った純リストになるということをそのまま利用するのである。

(defun my-length (L)
  (cond ((null L) 0)
        (t (1+ (my-length (cdr L))))))

このように自分を定義するために自分自身を利用することを「再帰的定義」という。

純リスト自体が再帰的な構造をしているので、 純リストを扱うプログラムも再帰アルゴリズムで記述しやすいのである。

ついでにこの関数をもとにして「リスト中の全アトムの数を返す関数」を作ろう。 つまり

で4を返す関数だ。

やることは簡単で、要素がリストだったら自分自身を使ってリスト中の要素を数えるのである。

(defun length2 (L)
  (cond ((null L) 0)
        ((listp (car L)) (+ (length2 (car L)) (length2 (cdr L))))
        (t (1+ (length2 (cdr L))))))

次に、リストを作る関数を定義してみる。例えば

のような文字列を要素とした任意長のリストから、

各要素の文字列の長さを要素としたリストを作る。

リストを扱う関数を作るコツは、まず空のリストを与えられた場合について考え、 次にリストの長さが1減ったリストとの関係を見つけ出すことである。 この場合、空のリストを与えられたら空のリストが返ればよい。 長さが1つ短いリストの結果のリストの先頭に先頭要素の文字列の長さを入れると結果となる (図4)。

図4: リストを作る

(defun string-to-length (L)
  (cond ((null L) nil)
        (t (cons (length (car L)) (string-to-length (cdr L))))))

文字列の長さを返す関数は length だ。 リストの長さを返す関数も length だが、 リストが与えられたときはリストの長さ、 文字列が与えられたときは文字列の長さを返すようになっている。 cons に要素とリストを渡せばリストを作ることができる。

の評価結果は

である。