cons (Lisp)

ウィキペディア

cons (Lisp)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/08/24 10:54 UTC 版)

consは、ほとんどのLisp方言における基本的な関数である。cons は、2つの、値もしくは値へのポインタを保持するオブジェクトを構成(construct)する。これによって作られたオブジェクトは、(cons)セル、cons、non-atomic S式(NATS式)、(cons)対などと呼ばれる。cons の結果のペアの左側(第一要素)は carと呼ばれ、右側(その残り)は cdrと呼ばれる。

使い方

cons 自体は単に、データの順序対を保持することができるだけだが、しばしばリストや二分木などの複雑なデータ構造を保持するためにも使われる。

例えば、Lisp の式、(cons 1 2) は、左側(car部)に1 、右側(cdr部)に2 を持ったcons セルを作る。Lisp の表記では、(cons 1 2) の値は次のようになる:

(1 . 2)

1 と2 の間に. があるのに注意。これはこのS式が、「リスト」ではなく「ドット対」であることを示している。

リスト

リスト(42 69 613) を表すcons セルダイヤグラム
cons を使って書いた場合:

(cons 42 (cons 69 (cons 613 nil)))

list を用いた場合:

(list 42 69 613)

Lisp において、cons はリストを実装するための基本的な構造である。具体的には、Lisp においては全てのリストは以下のいずれかである:

1. 一般に nil と呼ばれる特別なオブジェクトである空のリスト ()
2. car としてリストの第一要素を持ち、 cdr としてリストの残りの要素を持つ cons セル

この構造は、単純な片方向連結リスト構造を作る。この連結リストは、 cons, car, cdr のみで操作することのできる構造をしている。nil は cons 対でない唯一のリストであることに気をつけなければならない。例として、1, 2, 3 の要素から成るリストを考えよう。そのようなリストは、以下の3ステップで作られる。

1. 3 とnil(空リスト)のcons を作る。
2. 2 とその結果とのcons を作る。
3. 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

関連項目

• LISP
• CARとCDR
• コンストラクタ
• 代数的データ型
• Hash consing

外部リンク

• SDRAW, Common Lisp code for drawing draws cons cell structures. From David S. Touretzky.