Lisp の Sequence 型のまとめ

Common Lisp のソート関数や探索関数は,引数にシーケンス(SEQUENCE)型のオブジェクトを取る.シーケンス型はベクトル(VECTOR)型とリスト(LIST)型の抽象型なので,ベクトルとリストのいずれもそれら関数に渡すことが出来る.では配列(ARRAY型)を引数に渡したい場合はどうか? Common Lisp ではベクトルは 1 次元配列と同じなので,シーケンスを引数に取る関数に 1 次元配列を渡すのは問題ない.

Common Lisp における配列とベクトルの違い
  • VECTOR は 1 次元配列のこと.つまり 1 次元の ARRAY を作成すれば VECTOR になる.

  • SEQUENCE は 1 次元に並んだコレクションの総称ということになる.

シーケンス 型のクラス階層

シーケンス型は,ベクトル型とリスト型の親クラスで,ベクトルとリストの共通インタフェースを提供する.文字列(STRING)型はベクトル型のサブクラス(CHARACTER 型を要素とするベクトル)なので,文字列型にもシーケンス型のインタフェースを適用できる.

コード 1. SEQUENCE 型のクラス階層
sequence
   +-- list  (要素のアクセスは線形時間 O(n) )
   +-- vector(要素のアクセスは定数時間 O(1) ) == 1次元配列(one-dimensional array)
          +-- string     (要素がcharacter型のベクトル)
          +-- bit-vector (要素がbit型のベクトル)

STRING 型は要素の型を CHARACTER 型に特定化した VECTOR 型だ.VECTOR 型は 1 次元の ARRAY 型と同じなので,STRING 型も make-array を使って作成できる.

(type-of (make-array 5 :element-type 'character))    ; -> (SIMPLE-ARRAY CHARACTER (5))
(typep (make-array 5 :element-type 'character) 'string)         ;-> T
(typep (make-array 5 :element-type 'character) 'simple-string)  ;-> T

VECTOR 型(1 次元の ARRAY 型),STRING 型,BIT-VECTOR 型はさらに,SIMPLE 版のデータ型が存在する.

通常版 SIMPLE 版

1次元のARRAY 型

SIMPLE-ARRAY 型

VECTOR 型

SIMPLE-VECTOR 型

STRING 型

SIMPLE-STRING 型

BIT-VECTOR 型

SIMPLE-BIT-VECTOR 型

SIMPLE 版と通常版の違いは,SIMPLE 版は fill-pointer がなく,adjustable ではなく,displaced-to が指定されていない点である.

fill-pointer

現在の要素数を保持する機能.プッシュやポップといったスタックのインターフェースを使用する際に必要になる.

adjustable

adjust-array で要素数を変更できる.

displaced-to

指定されたターゲットオブジェクトに要素が設定される.

以上がシーケンス型ファミリーの概観である.ソートや探索などコレクション・オブジェクトに対する関数は通常シーケンス型を引数に取る.シーケンス型の共通インタフェースは以下の通りである.

Table 1. SEQUENCE 型の共通インタフェース(sequence function)

concatenate

copy-seq

count

count-if

count-if-not

delete

delete-duplicates

delete-if

delete-if-not

elt

every

fill

find

find-if

find-if-not

length

map

map-into

merge

mismatch

notany

notevery

nreverse

nsubstitute

nsubstitute-if

nsubstitute-if-not

position

position-if

position-if-not

reduce

remove

remove-duplicates

remove-if

remove-if-not

replace

reverse

search

some

sort

stable-sort

subseq

substitute

substitute-if

substitute-if-not

シーケンス型の留意点
  • シーケンスに共通のアクセサは elt だが,各サブタイプ向けに最適化されたアクセサが用意されている.

  • simple- が付いているデータ型はフィルポインタが無く*伸縮不可能*なデータ構造.

以下にコンストラクタとアクセサをまとめた.表には代表的なコンストラクタを 1 つだけ載せた.しかし,全て 1 次元配列の特殊版なので,どれも make-array で作成できる.表の後に別の作成方法の解説を付している.

コンストラクタ アクセサ フィルポインタ 伸縮可能

sequence

make-sequence

elt

有/無

可/不可

vector(1次元array)

make-array

aref

simple-array(1次元のみ)

make-array

aref

不可

simple-vector

make-array

svref

不可

string

make-array

char

simple-string

make-string

schar

不可

bit-vector

make-array

bit

simple-bit-vector

simple-bit-vector

sbit

不可

作成方法(n は要素数)
sequence

(make-sequence タイプ n) タイプは listvector のサブタイプ.

vector

(make-array n :fill-pointer t)

simple-array

(make-array n):adjustable:fill-pointer:displaced-to のデフォルト値は全て nil なので指定の必要はない.simple-arrayvector と同じ構造だがクラス階層では vector のサブクラスではないので make-sequence は使えない.ただし,typepsimple-array 型のオブジェクトも simple-vector 型のオブジェクトも区別なく t を返す.

simple-vector

(vector 要素 要素 …​)(make-sequence 'simple-vector n)(make-sequence 'vector n),または simple-array と同じ作成方法.

string

(make-array n :element-type 'character :fill-pointer t)

simple-string

(make-string n)(make-sequence 'simple-string n)(make-sequence 'string n)

bit-vector

(make-array n :element-type 'bit :fill-pointer t)

simple-bit-vector

(make-sequence 'simple-bit-vector n)(make-sequence 'bit-vector n)

留意点
  • SIMPLE 版のデータ構造は通常版のサブクラスでもあるので,fill-pointeradjustable を使わないなら SIMPLE 版のデータ構造を通常版のデータ構造として使える.

  • fill-pointer を使わないなら,make-sequence にサブタイプを指定して 作成できる.

  • make-sequencefill-pointer オプションを指定できないため,simple ではないシーケンスのサブタイプを作成するには make-array で型を指定して :fill-pointert に設定する.

  • 上のリストには simple なデータ型に make-array を使った作成方法記述していな いが,make-array:fill-pointer のデフォルト値は nil なので, :fill-pointer を省略すれば自動的に simple なデータ構造になる.

  • シーケンスなら何でも作れる万能コンストラクタは make-array