Lispの話(リスト)

こんにちは、たくさん寝太郎です。

気付けば夏休みも残り3週間となってしまいました。
台風21号からそろそろ1週間経過し、知り合いの家もほぼ電気が復旧したそうで何よりです。

さて、今日はリストの話をします。

ドットリスト・循環リスト・連想リスト

以前データ型の話で単純なリストの話をしましたが、Lispには他にも特別な種類のリストが存在します。

ドットリスト

Lispのリストはコンスセルから作られており、次の2つは同じリストを表しています。

(1 2 3)
(cons 1 (cons 2 (cons 3 nil)))

これを図で表すと次のようになっています。(作ってみた)

では次のようなリストを考えてみましょう。

(cons 1 (cons 2 3))

=>(1 2 . 3)

ドットが出てきました。これはリストの終端がnilでないことを表しており、このようなものをドットリストと言います。

対

ドットリストの実用的な使い方として対の表現があります。
次の2つのコードを考えてみましょう。

(cdr '(1 2))
(cdr '(1 . 2))

上は(2)を返し、下は2を返します。
後者は2つの要素をつなぐのに1つだけコンスセルをアロケートすれば良いので効率が良くなります。

循環リスト

リストの終端のコンスセルのcdrが最初のコンスセルを指すようなリストを考えてみましょう。

このようなリストを循環リストと呼びます。
Common Lisp環境で循環リストを試す前には必ず次のコマンドを実行しておきます。(実行しないと無限ループに陥ってしまいます。)

(setf *print-circle* t)

循環リストを作る最も直接的な方法はsetfを使いリストの終端(nil)を先頭を指すように書き換えることです。

(defparameter foo (list 1 2 3))
(setf (cdddr foo) foo)

=> #1=(1 2 3 . #1#)

連想リスト

keyと値の対のリストを連想リスト(association list)と言いalistと呼びます。

(defparameter *food-order* '((tanaka . hamburger)
                           (saitou . sushi)
                           (mogi . beef)))

keyから値を得るにはassocを使います。

(assoc 'mogi *food-order*)

=> (MOGI . BEEF)

keyに対応する値を変更するにはpushを使います。

(push '(saitou . ramen) *food-order*)

=>
((SAITOU . RAMEN)
 (TANAKA . HAMBURGER)
 (SAITOU . SUSHI)
 (MOGI . BEEF))

慣習的に同じkeyが複数含まれているときは最初のkeyのみを有効にします。
pushは既にあるリストの前に新しい要素を追加するだけで以前のkeyと値は消さないので、後からデータの変更履歴を辿ることができます。

このようにalistは便利なものですが、大きなリストのデータを取り出すにはあまり効率の良い方法ではありません。

次回はデータの読み書きの話をしようと思います。

Land of Lisp