Scheme第11歩

ベクタと連想リストの話。

まずは、序盤にさらりと触れたっきりだったベクタについて。ベクタとは固定長の配列。作成するには#()リテラルか

(vector 要素 ...)
(make-vector 要素数)
(make-vector 要素数 各要素の初期値)

を使う。make-vector初期値を省略すると#<undef>になる模様。
こうして作成したベクタの長さは

(vector-length ベクタ)

で得られる、要素の取得と設定は

(vector-ref ベクタ インデックス)
(vector-set! ベクタ インデックス 設定したい値)

とする。ベクタのインデックスは0オリジン。例えば、長さが10なら有効なインデックスは0～9。vector-refもvector-set!も、無効なインデックスの値を指定するとエラーとなる。
ベクタの複製は

(vector-copy ベクタ)
(vector-copy ベクタ 先頭インデックス)
(vector-copy ベクタ 先頭インデックス 末尾インデックス)

で行う。先頭インデックスは省略すると0、末尾インデックスは省略すると(長さ-1)となる。インデックスが範囲外を指し示した場合、無効なインデックスに対応する要素は#<undef>。
ベクタからリストへ、リストからベクタへの変換は

(vector->list ベクタ)
(list->vector リスト)

とする。

ベクタとリストの使い分けは、まあ適材適所か。処理系の実装依存ではあるだろうけれど、大量のデータをランダムアクセスする場合はベクタが向いているだろう。一方、 伸ばしたり縮めたり、千切ったり繋げたりするのはリストの得意技。

連想リストはドット対のリスト。ベクタのように専用の型があるわけでなく、あくまでリストの一種。他のリストとの違いは、連想リスト専用の探索関数が用意されていること。例えば

(define al '((foo . 123) (bar . 456) (baz . 7890)))

という連想リストに対して

(assq 'bar al)

とすると、

(bar . 456)

という値が得られる。要するに、他の言語で言うところの連想配列と同じようなもの。ただし実装はあくまで連結リストなので、探索時間はO(n)。
連想リストの探索関数にはassq, assv, assocがある。これらの違いはキーの比較方法。前から順にeq?, eqv?, equal?で比較する。