12

Common Lisp Cons Cell の正確な定義は何ですか? コンス セルは、標準のリンク リスト アイテムとどう違うのですか? 結局のところ、コンス セルとリンクされたリスト アイテムの両方に、値と次のセルまたはアイテムへのポインターがあります... それとも、この理解は間違っていますか?

4

5 に答える 5

20

一般に、コンス セルは、任意のものを指すことができる 2 つのポインターを保持します。もちろん、一般的な使用法は、左のもので「値」を指し、「右」のもので別の Cons セル (または nil) を指すことです。

于 2009-08-22T21:00:37.657 に答える
14

コンス セルは、リンク リスト ノードよりもバイナリ ツリー ノードに近いです。car と cdr は、nil、アトム、またはその他のコンス セルの 2 つの子を返します。

于 2009-08-22T21:04:44.277 に答える
7

Lisp では、コンス セルは値のペアを保持します。コンスセルが変数内にある場合c、(car c)最初の値を(cdr c)返し、2 番目の値を返します。

慣例により、リストはコンス セルで構成されcarます。セルの にはノード値がcdr含まれ、次のノードへの参照またはリストの終わりを示す nil (空のリスト) が含まれます。プリミティブ関数がリストを返すか受け入れる場合、これはリストが表示される形式です。

したがって、 listのl場合(car l)、最初の要素 (最初のコンス セルの値) を与え、リスト(cdr l)の末尾 (リスト内の次のコンス セル) を返します。

于 2009-08-22T21:19:37.663 に答える
7

セルは、 、、およびでcons構成されるコントラクトの 3 分の 1 であり、他の人が述べたように、それらがペアとして動作する必要があります。conscarcdr

この定義から「参照」、「ポインタ」などの単語を除外する理由は、それらが実装の詳細であることを認識するためです。cons必要に応じて、Abelson と Sussman が行ったように、何もないところから構築できます。

(define (cons a b) (lambda (x) (x a b)))
(define (car x) (x (lambda (a b) a)))
(define (cdr x) (x (lambda (a b) b)))

この定義は完全に Lisp の定義と関数の世界の中にあり、オブジェクトが値として格納されているか参照として格納されているかを考慮することさえやめません。ただし、これらはプリミティブ オブジェクトのドロップイン置換として機能します (可変性やその他の特別な用途は考慮されていません)。

于 2009-09-08T03:55:22.497 に答える
4

ここでの他の回答は正確ですが、1つのことについて明確ではないと思います。

従来の C++ リンク リストの実装では、2 つのフィールド (valとnextなど) はtypedです。nextターミネータを使用して、リスト内の別のノードを指すように定義されnullています。で別のノード以外を指すことはできませんnext。

Lisp は動的に型付けされるため、コンス セルのどちらのフィールドも(アトムまたは参照のいずれか)何でもかまいません。コンス セルを使用して連結リストを実装できます (つまり、Lisp リストとは: ターミネータ付きのコンス セルのチェーンですnil)。ただし、コンス セルを座標ペア、ツリー ノードとして使用して、各フィールドに任意の値を入れることもできます。など

これらを組み合わせることもできます。たとえば、x y座標のリスト:

;; (cons foo (cons bar nil)) == (list foo bar)    
(cons
  (cons 5 4)
  (cons (cons 9 10) nil))
=>
((5 . 4) (9 . 10))

したがって、コンスセルはリンクリストノードよりも厳密に一般的です。いわば「適用されたペア」に近いです。すべての標準的なリスト処理関数 ( map、dolistなど) は、値を に入れ、別のリストを に入れることを想定した単純な関数です。carcdr

これはすべて、必要に応じて、次のコンスセルを指し、値を指して、リストを逆方向に定義できることを意味します! リンク リスト ノードでこれを行うには、クラスまたはデータ構造を再定義して型を変更する必要があります。carcdr

于 2009-09-08T03:42:21.353 に答える