Menu

Subscribe

Lisp の Sequence 型のまとめ

on #lisp #programming
目次

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) タイプは list か vector のサブタイプ．

vector

(make-array n :fill-pointer t)

simple-array

(make-array n)．:adjustable，:fill-pointer，:displaced-to のデフォルト値は全て nil なので指定の必要はない．simple-array は vector と同じ構造だがクラス階層では vector のサブクラスではないので make-sequence は使えない．ただし，typep は simple-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-pointer や adjustable を使わないなら SIMPLE 版のデータ構造を通常版のデータ構造として使える．

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

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

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

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