リスト - Alexandria

概要

このページでは、Common Lispの汎用ユーティリティであるAlexandriaの「リスト」構造に関するオペレータを紹介します。

alist-plist関数: 連想リストを属性リストに変換

Alexandriaのalist-plist関数は名前の通り連想リストを属性リストに変換します。
(alexandria:alist-plist '((a . 1) (b . 2) (c . 3)))
; => (A 1 B 2 C 3)

plist-alist関数: 属性リストを連想リストに変換

plist-alist関数は逆に属性リストを連想リストに変換します。
(alexandria:plist-alist '(a 1 b 2 c 3))
; => ((A . 1) (B . 2) (C . 3))

assoc-valueアクセッサ: setfマクロに対応したassoc

ANSI Common Lispではassocという連想リストへの参照を行う関数が定められています(第14章「リスト」)。この関数は連想リストからkeyを手がかりに(key . value)のコンス(エントリー)を取得するものです。

Alexandriaのassoc-value関数はANSI標準のassocに対して2つの拡張が施されています。

  • 返り値は多値であり、1番目の返り値はvalueのみを、2番目の返り値がエントリーを返します。
  • setfマクロにも対応しているため、値の変更が簡単にできます。
特に2つ目の拡張は連想リストを使う場合には大変便利です。以下に例を示します。

;; ALIST の準備
(defparameter *alist* nil)
; => *ALIST*

;; エントリーの追加
(setf *alist* (acons 'a 1 *alist*))
; => ((A . 1))

;; ANSI標準の assoc でもアクセスは容易にできる
(assoc 'a *alist*)
; => (A . 1)

;; Alexandriaの assoc-value の返り値は多値
(alexandria:assoc-value *alist* 'a)
; => 1 ;
;    (A . 1)

;; setf で変更ができるため便利
(setf (alexandria:assoc-value *alist* 'a) 2)
; => 2
*alist*
; => ((A . 2))

rassoc-valueアクセッサ: valueベースのassoc-value

ANSI Common Lispにはassocと同様にrassoc関数が定められており、keyではなくvalueを基にエントリーを参照することができます。Alexandriaのrassoc-valueアクセッサもvalueを基に参照します。上の例に続いて、以下のサンプルを実行してみてください。
(alexandria:rassoc-value *alist* '2)
; => A ;
;    (A . 2)

doplistマクロ: 属性リストに対する繰り返し

属性リストはkeyvalueが交互に現れる普通のリストであるため、繰り返しの処理は比較的用意ですが、Alexandriaのdoplistを使うと最も簡潔かつ明瞭に属性リストに対する繰り返しを行うことができます。
(defparameter *plist* '(a 1 b 2 c 3))
; => *PLIST*

(alexandria:doplist (k v *plist*) (format t "~a: ~a~%" k v))
; A: 1
; B: 2
; C: 3
; => NIL

各種モディファイマクロ

AlexandriaではANSI Common Lisp標準の関数に対してモディファイマクロが追加されています。モディファイマクロとは、変数の変更を伴うことができるオペレータです。

Macro: appendf
append関数のモディファイマクロ
Macro: nconcf
nconc関数のモディファイマクロ
Macro: unionf
union関数のモディファイマクロ
Macro: nunionf
nunion関数のモディファイマクロ
Macro: reversef
reverse関数のモディファイマクロ
Macro: nreversef
nreverse関数のモディファイマクロ

例えばappendnconcの違いはリストをコピーしてから連結するか、破壊的に修正して連結するかの違いで、それぞれの返り値を使うことが前提であることに変わりはありません。つまり、引数を再利用するか、という点が破壊的な修正を行うべきかの判断基準になります。unionnunionreversenreverseなどの関係も同様です。(参考:第14章「リスト」)

他方、Alexandriaが提供するのはモディファイマクロなので、返り値を使うことを前提とするのではなく、変数の束縛を変更することを前提に使用されます。つまり、appendnconcで得た返り値をsetfsetqで束縛するなら、代わりにAlexandriaのappendfnconcfを使った方が美しく書ける、ということです。

以下にサンプルを示します。
(defparameter *list* '(1 2))
; => *LIST*

;; ANSIの append は変数の束縛状況を変更しない
(append *list* '(3 4))
; => (1 2 3 4)

;; 変わっていない
*list*
; => (1 2)

;; Alexandriaの appendf は変数の束縛状況を変更できる
(alexandria:appendf *list* '(3 4))
; => (1 2 3 4)

;; 変更されている
*list*
; => (1 2 3 4)
ちなみに、union関数は標準仕様入門では説明していませんが、リストを集合とみなす関数です。
(union '(a b c) '(d c e))
; => (A B D C E)

circular-list関数: 循環リストの生成

Alexandriaのcircular-list関数は手軽に循環リストを生成するオペレータです。循環リストとは、リストの一番最後の参照が一番最初に繋がっているデータ構造で、循環構造を本質的に表すことができます。動作(コード)では「無限ループ」と呼ばれるものがありますが、循環リストは「無限データ」です。

循環リストを扱うときはあらかじめ*print-circle*スペシャル変数をtに変更しておく必要があります。これをしないと通常のリストのように表示しようとして、無限ループに陥ります。

Alexandriaのcircular-list関数で循環リストを生成し、ANSI標準のpopマクロで値を取り出す例を示します。循環リストは本質的に無限なので、popで値を取り出しても終わりはありません。

;; 必ずスペシャル変数を変更すること!
(setq *print-circle* t)
; => T

;; Alexandriaの circular-list 関数で循環リストを生成する
(defparameter *circle* (alexandria:circular-list 1 2 3))
; => *CIRCLE*

;; 循環リストの表記は以下の通り
*circle*
; => #1=(1 2 3 . #1#)

;; pop し続けても終わらない
(pop *circle*)
; => 1
(pop *circle*)
; => 2
(pop *circle*)
; => 3
(pop *circle*)
; => 1
(pop *circle*)
; => 2
(pop *circle*)
; => 3

make-circular-list関数: 初期値による循環リストの生成

Alexandriaのcircular-list関数は引数から循環リストを生成しますが、make-circular-list関数は要素数と初期値から循環リストを生成します。
(setq *print-circle* t)
; => T

(alexandria:make-circular-list 3 :initial-element 0)
; => #1=(0 0 0 . #1#)

circular-list-p関数: 循環リストの判定

circular-list-p関数は循環リストであるかどうかを判定します。上の例に続けて、以下のサンプルを試してみてください。
(alexandria:circular-list-p *circle*)
; => T

proper-list-p関数: プロパーリストの判定

Alexandriaのproper-list-p関数はproper listであるかどうかを判定します。プロパーリストとは、最後のセルのCDR部がnilになっているリストです。
;; 一般的なリスト表記によるプロパーリスト
(alexandria:proper-list-p '(1 2 3))
; => T

;; 最後のコンスのCDR部がnilではないインプロパーリスト
(alexandria:proper-list-p '(1 2 . 3))
; => NIL

;; プロパーリストのコンス表記
(alexandria:proper-list-p '(1 . (2 . (3 . nil))))
; => T

;; インプロパーリストのコンス表記
(alexandria:proper-list-p '(1 . (2 . (3 . 4))))
; => NIL

;; nilはプロパーリスト
(alexandria:proper-list-p nil)
; => T

ensure-car関数: CAR部またはオブジェクトそのものの取得

ensure-car関数は引数がリスト(コンス)の場合はCAR部を、そうでないなら引数そのものを返すオペレータです。ANSI標準のcar関数は引数がリストでない場合にエラーを通知しますが、ensure-carはエラーを通知しないという違いがあります。
(alexandria:ensure-car 1)
; => 1

(alexandria:ensure-car '(1 2))
; => 1

ensure-cons関数: コンスの取得

ensure-cons関数は引数がリスト(コンス)の場合は引数そのものを、そうでないならCDR部をnilとするコンスを返します。ANSI標準のcons関数は引数が2つですが、ensure-consは引数が1つです。
(alexandria:ensure-cons 1)
; => (1)

(alexandria:ensure-cons '(1 2))
; => (1 2)

ensure-list関数: リストの取得

ensure-list関数がensure-cons関数と違うのは、nilに対する動作だけです。

ANSI Common Lispではcons型はnilを含まず、list型はnilを含むと定められています(第14章「リスト」)。そのため、ensure-cons関数でnilを引数に渡すとコンスではないと判断され、'(nil . nil)というコンスが、つまり'(nil)が生成されます。他方、ensure-list関数でnilを引数に渡すとリストであると判断されるため、引数であるnilがそのまま帰ってきます。
(alexandria:ensure-cons nil)
; => (NIL)

(alexandria:ensure-list nil)
; => NIL

一般に説明文の中でリストやコンスという言葉を使うときは明示的な区別をせず使いますが、型としてのconslistは包含関係になっていますので注意してください。

remove-from-plist関数: 属性リストからの削除

属性リストからkeyを手がかりにエントリーを削除するにはremove-from-plist関数を使います。
(alexandria:remove-from-plist '(a 1 b 2 c 3) 'b 'c)
; => (A 1)

第2引数以降は可変長ですので、いくつでも指定して削除することができます。

delete-from-plist関数: 属性リストからの破壊的な削除

delete-from-plist関数は前節のremove-from-plist関数と似た動作をしますが、引数を破壊的に修正する点が異なります。
(defparameter *plist* '(a 1 b 2 c 3))
; => *PLIST*

(alexandria:delete-from-plist *plist* 'b)
; => (A 1 C 3)

*plist*
; => (A 1 C 3)

勘違いしやすい点ですが、破壊的な動作を伴う関数をモディファイマクロのように使用してはいけません。破壊的な修正は一般に引数を再利用しない場合に使用するもので、引数の変更はあくまで副次的な過程で発生する「副作用」です。このような関数は破壊的ない(コピーを行う)関数と同様に返り値を使用することが大前提です。

remove-from-plistf, delete-from-plistfマクロ: モディファイマクロ

変数に束縛された属性リストからエントリーを削除し、改めてその変数に束縛し直すためのモディファイマクロは関数とは別に定められています。使い方は同じですが、こちらはモディファイマクロなので、引数を返り値で束縛し直すという点が特徴的です。remove系とdelete系の違いは引数をコピーするかどうかです。

mappend関数: appendを用いるmapcan

ANSI Common Lispにはmapcanという高階関数が定義されており、リストの各要素に第1引数の関数を適用し、返り値のリストをnconc関数で連結するというオペレータです。第14章「リスト」にサンプルを掲載していますので、参照してください。

Alexandriaのmappend関数はリストの連結にappendを用いる点が異なります。下の方で紹介するmap-product関数の実装に使用されています。。

(alexandria:mappend #'identity '((1 2)(3 4)(5 6)))
; => (1 2 3 4 5 6)

(alexandria:mappend #'cdr '((1 2)(3 4)(5 6)))
; => (2 4 6)

(alexandria:mappend #'(lambda (v) `(,(car v))) '((1 2)(3 4)(5 6)))
; => (1 3 5)

setp関数: 重複のないリストであるかの判定

Alexandriaのsetp関数は、引数のリストの要素に重複がないかどうかを判定する述語関数です。リストでない場合や重複がある場合にnilを返し、重複のないリストである場合にtを返します。なお、nilに対しては空集合としてtを返します。

以下にサンプルを示します。
(alexandria:setp '(a b c))
; => T

(alexandria:setp '(a b a))
; => NIL

(alexandria:setp nil)
; => T

set-equal関数: 2つのリストの要素が同じであるかの判定

set-equal関数はリストを2つ引数に取ります。そして、両方のリストに含まれる要素が同一であればtを、そうでなければnilを返します。

片方の要素が別のリストに含まれない場合はnilとなりますが、重複は許容するため、要素数が異なるだけでnilになることはありません。以下のサンプルで確認してください。
(alexandria:set-equal '(a b c) '(b c a))
; => T

;; 同じ要素を持つなら要素数が異なっていても t となる
(alexandria:set-equal '(a b c) '(a b c a))
; => T

(alexandria:set-equal '(a b c) '(a b c d))
; => NIL

map-product関数: 直線的なマッピング

ANSI Common Lispの標準仕様ではmapcarという定番の高階関数が定められています。この関数は引数のリストの各要素に対して並列的に関数を適用し、結果として一つのリストを返します。

下の例を見れば分かるように、'aを取り出す時には同時に'cを、'bを取り出すときには同時に'dを取り出します。
(mapcar #'list '(a b) '(c d))
; => ((A C) (B D))

Alexandriaのmap-product関数は組み合わせを考えるアルゴリズムに近く、1つの要素を固定して、残りの全ての要素との組み合わせを取りながら関数を適用します。
(alexandria:map-product #'list '(a b) '(c d))
; => ((A C) (A D) (B C) (B D))

上の例では、'aを取り出す時には'cのみならず'dも取り出され、'bを取り出す時にも同様に'c'bが取り出されているのが分かります。

productという言葉から行列やベクトルの積を思い浮かべるかもしれませんが、必ずしも計算とは無関係です。例えば、リストを数学上のベクトルと見なし、手前のリストを行ベクトル、2つ目のリストを列ベクトルと見なした場合、ANSI Common Lispのreducemapを使うだけで簡単に実装できます。

(defun vector-product (x y) (reduce #'+ (map 'vector #'* x y)))
; => VECTOR-PRODUCT

;; (1 * 3) + (2 * 4) = 11
(vector-product '(1 2) '(3 4))
; => 11

;; リスト構造でもベクトル構造でも使える
(vector-product '(1 2) #(3 4))
; => 11

flatten関数: 複雑なリスト構造の単純化

再帰の練習などでよく見かける「フラット化」のための関数もAlexandriaには用意されています。flattenです。
(alexandria:flatten '((1 (2 3)) (4 (5 (6 7 8) 9) 10)))
; => (1 2 3 4 5 6 7 8 9 10)

0 件のコメント :

コメントを投稿