common-lisp
リストの種類
サーチ…
プレーンリスト
Plainリストは、Common Lispの中で最も単純なタイプのリストです。それらは要素の順序付けられたシーケンスです。彼らは、リストの最初の要素を取得する、リストの残りの部分を一定時間に取得する、線形時間でランダムアクセスをサポートするなどの基本的な操作をサポートしています。
(list 1 2 3)
;=> (1 2 3)
(first (list 1 2 3))
;=> 1
(rest (list 1 2 3))
;=> (2 3)
リストの要素だけを気にする限り、 "平らな"リストで動作する多くの関数があります。これらには、 find 、 mapcar 、その他多くのものが含まれます。 (これらの関数の多くは、これらの関数のいくつかについても17.1 Sequence Conceptsで動作します。
関連リスト
プレーン・リストは一連の要素を表現するのに便利ですが、時にはバリュー・マッピングの一種のキーを表す方が便利な場合もあります。 Common Lispには、純粋なハッシュテーブル( 18.1ハッシュテーブルの概念を参照)を含むいくつかの方法があります。 Common Lispのkey to valueマッピングには 、 プロパティリストと関連リストという2つの主要な方法があります 。この例では、関連リストについて説明します。
アソシエーションリスト、またはalistは、各ペアのカーがキーであり、各ペアのcdrが関連する値である点線のペアである要素を持つ "プレーン"リストです。例えば、
(defparameter *ages* (list (cons 'john 34) (cons 'mary 23) (cons 'tim 72)))
個人名を示すシンボルを年齢を示す整数でマッピングする関連リストと考えることができる。 メンバーのような単純なリスト関数を使っていくつかの検索関数を実装することは可能です。たとえば、 ジョンの年齢を取得するには、
(cdr (first (member 'mary *age* :key 'car)))
;=> 23
メンバ関数は、その車 メアリーである、すなわち、((メリー。23)(TIM。72))短所細胞と始まるリストの末尾を返し、 最初の (メアリーであるリストの最初の要素を返します。 23) 、 cdrはそのペアの右側を返します。これは23です。これは関連リストの値にアクセスする方法の1つですが、関連リストのような規約の目的は、基礎となる表現(リスト)から抽象化し、データ構造を扱うためのより高いレベルの関数を提供することです。
関連リストの場合、検索関数はassocであり、これはキー、関連リスト、オプションのテストキーワード(key、test、test-not)を受け取り、対応するキーのペアを返します。
(assoc 'tim *ages*)
;=> (tim . 72)
アイテムが存在する場合、結果は常にコンスセルになるため、 assocがnilを返すと、アイテムはリストに含まれません。
(assoc 'bob *ages*)
;=> nil
アソシエーションリストの値を更新するには、 setfをcdrとともに使用することができます。例えば、 ジョンの誕生日が到来し、年齢が上がると、次のいずれかが実行されます。
(setf (cdr (assoc 'john *ages*) 35)
(incf (cdr (assoc 'john *ages*)))
incfはsetfに基づいているため、この場合は動作します。
アソシエートリストは、双方向マップの一種として使用することもできます。これは、逆アソーク関数rassocを使用して、キーと値のマッピングを値に基づいて検索するためです。
この例では、明示的にlistとconsを使用して関連リストを作成しましたが、 pairlisを使用して関連リストを作成することもできます。これは、キーとデータのリストを取得し、
(pairlis '(john mary tim) '(23 67 82))
;=> ((john . 23) (mary . 67) (tim . 82))
aconsを使用して、単一のキーと値のペアを関連付けリストに追加できます。
(acons 'john 23 '((mary . 67) (tim . 82)))
;=> ((john . 23) (mary . 67) (tim . 82))
assoc関数は、リストを左から右へ検索します。つまり、アソシエーション・リスト内の値をマスクしたり、リストの構造を更新することなく値をマスクすることができます。リストの始め。 acons関数はこのために提供されています:
(defvar *ages* (pairlis '(john mary tim) '(34 23 72)))
(defvar *new-ages* (acons 'mary 29 *ages*))
*new-ages*
;=> ((mary . 29) (john . 34) (mary . 23) (tim . 72))
そして今、 maryのルックアップが最初のエントリを返します:
(assoc 'mary *new-ages*)
;=> 29
プロパティリスト
プレーン・リストは一連の要素を表現するのに便利ですが、時にはバリュー・マッピングの一種のキーを表す方が便利な場合もあります。 Common Lispには、純粋なハッシュテーブル( 18.1ハッシュテーブルの概念を参照)を含むいくつかの方法があります。 Common Lispのkey to valueマッピングには 、 プロパティリストと関連リストという2つの主要な方法があります 。この例では、プロパティリストについて説明します。
プロパティリスト( plist )は、交互の値がキーとその関連値として解釈される「平易な」リストです。例えば:
(defparameter *ages* (list 'john 34 'mary 23 'tim 72))
個人名を示すシンボルと年を示す整数とをマッピングするプロパティリストと考えることができる。 メンバーのような単純なリスト関数を使っていくつかの検索関数を実装することは可能です。たとえば、 ジョンの年齢を取得するには、
(second (member 'mary *age*))
;=> 23
メンバ関数は、23であり、つまりメアリーで始まるリストの末尾、(メアリー23ティム72)、及び第二リターンそのリストの2番目の要素を返します。これはプロパティリストの値にアクセスする方法の1つですが、プロパティリストのような規約の目的は、基になる表現(リスト)から抽象化し、データ構造を操作するためのより高いレベルの関数を提供することです。
プロパティリストの場合、検索関数はgetfで、プロパティリスト、キー(より一般的にはインジケータと呼ばれます )、およびオプションのデフォルト値があり、プロパティリストにキーの値が含まれていない場合に返されます。
(getf *ages* 'tim)
;=> 72
(getf *ages* 'bob -1)
;=> -1
プロパティリストの値を更新するには、 setfを使用することができます。例えば、 ジョンの誕生日が到来し、年齢が上がると、次のいずれかが実行されます。
(setf (getf *ages* 'john) 35)
(incf (getf *ages* 'john))
incfはsetfに基づいているため、この場合は動作します。
プロパティリスト内の複数のプロパティを一度検索するには、 get-propertiesを使用します 。
getf関数は、リストを左から右へ検索します。 つまり 、プロパティリストの値をリストから削除したり、リストの構造を更新することなく "マスク"することができます。たとえば、 list *を使用すると:
(defvar *ages* '(john 34 mary 23 tim 72))
(defvar *new-ages* (list* 'mary 29 *ages*))
*new-ages*
;=> (mary 29 john 34 mary 23 tim 72)
そして今、 maryのルックアップが最初のエントリを返します:
(getf *new-ages* 'mary)
;=> 29