「CARとCDR」の版間の差分
削除された内容 追加された内容
m →概要 |
m →概要 |
||
9行目:
== 概要 ==
LISPにおいて、コンス（またはペア、またはドット対）は2つの要素を持つ[[順序対]]である。1番目の要素をCAR、2番目の要素をCDRと呼ぶ。リストは「CDRがリストであるコンス、または[[Null|空リスト]] <code>nil</code>」であると[[再帰的定義|再帰的に定義]]される<ref>COMMON LISP 第2版 p.25。なおCommon Lispでは最後の要素のCDRが空リストでないものは「ドットリスト」と呼ばれてリストとは別扱いされる。</ref>。
具体的にいうと、要素 <code><var>a</var></code> と <code><var>b</var></code> から構成されるコンスは <code>(<var>a</var> . <var>b</var>)</code> と表され、リスト <code>(<var>e<sub>1</sub></var> <var>e<sub>2</sub></var> <var>e<sub>3</sub></var>)</code> は、各要素を <code>car</code> 関数で取り出せるところのコンスセルと、後続のコンスセルを <code>cdr</code> 関数で取り出せるところの[[連結リスト|片方向リスト]]、すなわち <code>(<var>e<sub>1</sub></var> . (<var>e<sub>2</sub></var> . <var>e<sub>3</sub></var> . nil))</code> として実現されている。したがって、リストの先頭の要素を得るのは、最後の要素を得るのに比べて効率がよい。
| |||