common-lisp
Consセルとリスト
サーチ…
大会としてのリスト
一部の言語にはリストデータ構造が含まれています。 Common LispやLispファミリの他の言語は、リストを大量に使用しています(Lispという名前はLIStプロセッサの考え方に基づいています)。しかし、Common Lispは実際にはプリミティブリストデータ型を含んでいません。代わりに、慣例によりリストが存在する。大会は2つの原則に基づいています。
- シンボルnilは空のリストです。
- 非空のリストは、その車のリストの最初の要素であり、そのcdrがリストの残りの部分でコンスセルです。
それはリストにあるすべてです。あなたがコンスセルと呼ばれる例を読んだのであれば?その車がXで、そのcdrがYであるコンスセルが(X、Y)と書くことができます。つまり、上記の原則に基づいていくつかのリストを書くことができます。要素1、要素2、要素3のリストは単純に次のようになります。
(1 . (2 . (3 . nil)))
しかし、Lispファミリーの言語ではリストが非常に一般的であるため、コンスセルの単純なドット表記法以外の特殊な印刷規則があります。
- シンボルnilは()と書くこともできます。
- 1つのコンスセルのcdrが別のリスト( ()またはコンスセルのいずれか)である場合、1つのコンスセルに点線ペア表記を書き込むのではなく、「リスト記法」が使用されます。
リスト記法は、いくつかの例で最も明確に示されています。
(x . (y . z)) === (x y . z)
(x . NIL) === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ()) === (1)
リスト内の最後のcdrに達するまで、リストの要素は括弧内の連続した順序で書き込まれるという考え方です。最後のcdrがnil (空のリスト)の場合、最後のかっこが記述されます。最後のcdrがnilでない場合(この場合、リストは不適切なリストと呼ばれます )、ドットが書き込まれ、最後のcdrが書き込まれます。
コンスセルとは何ですか?
コンセルは、(印刷された表現のために)点対とも呼ばれ、単なる2つのオブジェクトのペアです。コンス・セルは、関数によって作成されたcons
、及び一対の要素は、関数を用いて抽出されたcar
およびcdr
。
(cons "a" 4)
例えば、これは最初の要素( car
で抽出できる)が"a"
で、2番目の要素( cdr
で抽出可能)が4
ペアを返します。
(car (cons "a" 4))
;;=> "a"
(cdr (cons "a" 4))
;;=> 3
短所セルは、 点線のペア表記で印刷することができます。
(cons 1 2)
;;=> (1 . 2)
コンスセルは点対記法でも読み取ることができるため、
(car '(x . 5))
;;=> x
(cdr '(x . 5))
;;=> 5
(コンスセルの印刷された形式も少し複雑になる可能性があります。詳細についてはコンスセルの例をリストとして参照してください)。
それでおしまい;コンス・セルは、関数によって作成された要素の単なるペアでcons
、および要素がで抽出することができcar
やcdr
。シンプルさのために、コンスセルは、より複雑なデータ構造のための有用なビルディングブロックになることができます。
コンスセルのスケッチ
コンスとリストの意味をよりよく理解するために、この種の構造のグラフ表示がしばしば使用されます。コンスセルは通常、接触している2つのボックスで表され、 car
とcdr
値を指す2つの矢印、または直接値を含みます。たとえば、次の結果が得られます。
(cons 1 2)
;; -> (1 . 2)
これらの図面の1つで表すことができます。
これらの表現は純粋に概念的なものであり、値がセルに含まれているか、セルから指し示されているということを示すものではないことに注意してください。一般的に、これは実装、値のタイプ、最適化のレベルなどによって決まります。残りの例では、一般的に使用されている最初の種類の図面を使用します。
したがって、たとえば:
(cons 1 (cons 2 (cons 3 4))) ; improper “dotted” list
;; -> (1 2 3 . 4)
次のように表される。
while:
(cons 1 (cons 2 (cons 3 (cons 4 nil)))) ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)
次のように表される。
ここに木のような構造があります:
(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4) ; note the printing as an improper list
最後の例は、この表記法が言語の重要なセマンティクスの側面を理解するのに役立つ方法を示しています。まず、前の例と同様の式を書いてみましょう。
(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)
通常の方法で表現することができます。
次に、別の表現を書いてみましょう。これは明らかに前のものと同じですが、これは結果の印刷表現によって確認されたようです。
(let ((cell-a (cons 1 2)))
(cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)
我々は図を描く場合でも、我々は表現の意味は同じセルが値であるため、異なっていることがわかりますの両方の car
一部とcdr
外側の一部cons
(これは、 cell-a
共有されています) :
2つの結果のセマンティクスが言語レベルで実際に異なるという事実は、次のテストによって検証できます。
(let ((c1 (cons (cons 1 2) (cons 1 2)))
(c2 (let ((cell-a (cons 1 2)))
(cons cell-a cell-a))))
(list (eq (car c1) (cdr c1))
(eq (car c2) (cdr c2)))
;; -> (NIL T)
第一eq
以来偽 car
とcdr
のc1
(つまりによって真である構造的に等しいequal
)が、第二の試験では結果がので真である間、(すなわち、「同一の共有構造」)「同一」ではありませんcar
やcdr
のc2
、彼らが同じ構造ですしている、 同じです。