Cons (Lisp)

Lispにおけるcons関数

Lisp方言において、cons関数はデータ構造の基本を形成する重要な要素です。この関数は、2つの値またはそれらのポインタを組み合わせて1つのオブジェクトを構成します。このオブジェクトは一般にconsセル、またはnon-atomic S式（NATS式）として知られています。consで生成されたペアは、左側の要素をcar（キャー）、右側の要素をcdr（シーダー）と呼びます。

consの基本的な使い方

cons関数は、データのペアを単純に保持することから始まりますが、実はリストや複雑なデータ構造の形成にも使用されます。たとえば、式「(cons 1 2)」を実行すると、左側に1、右側に2が持つconsセルが生成されます。この結果は次のように表されます：

```
(1 . 2)
```

ここで、要素の間にある「.」は、このS式がリストではなくドット対であることを示しています。

リストの構造

Lispでは、consを利用してリストを構成します。Lisp内のリストは主に以下の2種類になります：

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

この仕様により、単方向の連結リスト構造が形成されます。なお、nilはcons対ではない唯一のリストです。

たとえば、要素が1, 2, 3からなるリストを構成する流れは次の通りです：
1. 空リストnilに3を親要素としてzipする。
2. その結果に2を親要素としてzipする。
3. 上記の結果に1を親要素としてzipする。

そのため、作成されるリストは以下のような形となります：

```
(1 . (2 . (3 . nil)))
```

このリストは次のように略記されます：
```
(1 2 3)
```

要するに、consはすでに存在するリストの先頭に新しい要素を追加する機能を持っています。例えば、作成したリストをxとした場合、「(cons 5 x)」の結果は以下の通りになります：
```
(5 1 2 3)
```

また、append関数を使用すれば、二つのリストを結合することも可能です。

二分木の構築

consを用いることで、葉にだけ値を持つデータ構造である二分木も作成できます。たとえば、次のような記述を行うことで：
```
((1 . 2) . (3 . 4))
```

これにより、以下の構造を持つ二分木が作成されます：
```

/ \

---

/ \ / \
1 2 3 4
```

興味深いことに、リスト「(1 2 3)」もまた二分木と見なすことができ、その図は上記の構造に変形することで確認できます。

結論

Lispのcons関数は、リストや二分木といったデータ構造の生成において不可欠であり、この単純な関数の力を理解することで、より複雑なデータの取り扱いが可能になります。データの組織化や操作において、consは非常に強力です。これを活用して、様々なデータ構造を効率よく構築できます。

もう一度検索