Cons (Lisp)
consは、ほとんどのLisp方言における基本的な関数である。cons は、2つの、値もしくは値へのポインタを保持するオブジェクトを構成(construct)する。これによって作られたオブジェクトは、(cons)セル、cons、non-atomic S式(NATS式)、(cons)対などと呼ばれる。cons の結果のペアの左側(第一要素)は car[注釈 1]と呼ばれ、右側(その残り)は cdr[注釈 2]と呼ばれる。
使い方
cons 自体は単に、データの順序対を保持することができるだけだが、しばしばリストや二分木などの複雑なデータ構造を保持するためにも使われる。
例えば、Lisp の式、(cons 1 2)
は、左側(car部)に1 、右側(cdr部)に2 を持ったcons セルを作る。Lisp の表記では、(cons 1 2)
の値は次のようになる:
(1 . 2)
1 と2 の間に. があるのに注意。これはこのS式が、「リスト」ではなく「ドット対」であることを示している。
リスト
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Cons-cells.svg/350px-Cons-cells.svg.png)
cons を使って書いた場合:
(cons 42 (cons 69 (cons 613 nil)))
(list 42 69 613)
Lisp において、cons はリストを実装するための基本的な構造である。具体的には、Lisp においては全てのリストは以下のいずれかである:
- 一般に
nil
と呼ばれる特別なオブジェクトである空のリスト()
car
としてリストの第一要素を持ち、cdr
としてリストの残りの要素を持つ cons セル
この構造は、単純な片方向連結リスト構造を作る。この連結リストは、 cons
, car
, cdr
のみで操作することのできる構造をしている。nil
は cons 対でない唯一のリストであることに気をつけなければならない。例として、1, 2, 3 の要素から成るリストを考えよう。そのようなリストは、以下の3ステップで作られる。
- 3 と
nil
(空リスト)のcons を作る。 - 2 とその結果とのcons を作る。
- 1 とその結果とのcons を作る。
つまり:
(cons 1 (cons 2 (cons 3 nil)))
もしくはそれの短縮形として:
(list 1 2 3)
結果として、以下のリストが得られる:
(1 . (2 . (3 . nil)))
以下のような図で表すことができる。
*--*--*--nil | | | 1 2 3
このリストは、一般に以下のように略記される:
(1 2 3)
要するに、cons
は、すでに存在するリストの先頭に要素をひとつ付け加えるように働く。例えば、上で定義したリストをxとすると、(cons 5 x)
は、以下のようなリストを生成する。
(5 1 2 3)
もうひとつの便利なリスト操作関数として、 append
がある。それは、二つのリストを結合する。
木構造
葉の部分にのみ値を持つデータ構造である二分木もまた、cons
によって容易に作ることができる。例えば、以下のコードは
(cons (cons 1 2) (cons 3 4))
以下のような結果になる。
((1 . 2) . (3 . 4))
これはつまり、以下のような図で表すことができる:
* / \ * * / \ / \ 1 2 3 4
正確には、先ほどの例に出てきた(1 2 3) というリストもまた二分木である。それは、先ほどの図を少し変形することで容易にわかる:
*--*--*--nil | | | 1 2 3
これは、以下の図と同様である。
* / \ 1 * / \ 2 * / \ 3 nil
脚注
注釈
出典
関連項目
外部リンク
- SDRAW, Common Lisp code for drawing draws cons cell structures. From David S. Touretzky.
LISP系言語 | |
---|---|
言語(処理系) |
|
関連項目 |