お気楽 Scheme プログラミング入門

Scheme プログラミング中級編 [3]

今回は Scheme の「ベクタ (vector)」というデータ構造について説明します。ベクタは 1 次元配列のことで、手続き型言語ではおなじみのデータ構造です。Common Lisp は多次元配列を扱うことができますが、Scheme の仕様書 R5RS にはベクタ、R7RS-small にはベクタとバイトベクタしか規定されていません。

もっとも、ベクタがあれば多次元配列を実装するのは難しいことではありません。実際、Scheme には多次元配列を扱うライブラリ SRFI-25 がありますし、Gauche にも gauche.array というライブラリが用意されています。まず最初に「配列 (array)」について簡単に説明します。

●配列

配列はリストと同様に複数個のデータを格納することができます。配列に格納されたデータを「要素」と呼びます。リストは複数のコンスセルを接続して構成しますが、配列はデータを格納する変数を連続したメモリ領域に用意します。配列はホテルやマンションの部屋にたとえるとわかりやすいと思います。

ホテル全体を配列とすると、各部屋がデータを格納する変数と考えることができます。ホテルでは、ルームナンバーによって部屋を指定しますね。配列の場合も、整数値によってデータを格納する変数を指定することができます。この整数値を「添字 (subscripts)」といいます。


               図 : 配列の構造 (その１)

たとえば、10 個のデータを格納する配列を考えてみます。これは、平屋建てのマンションで、部屋が 10 室あると考えてください。この場合は上図に示すように、データを格納する変数が並んでいて、それぞれ 0 から 9 までの添字で指定することができます。

Lisp / Scheme の場合、添字は 0 から順番に数えます。ホテルのルームナンバーのように、4 や 9 は縁起が悪いから使わない、ということはありません。ほかのプログラミング言語、たとえばＣ言語は 0 から数えますが、PASCAL では 1 から数えます。

ところで、このマンションはたいへん好評で、隣の空き地に同じ建物を 2 つ新築しました。

ルームナンバーは 0 から 29 というように、通しで番号をつけてもいいのですが、A 棟 0 号室とか C 棟 9 号室のようにつけると、各部屋を区別することができます。この A 棟、B 棟、C 棟を 0, 1, 2 の整数値 (添字) に対応させると、各部屋は 2 つの添字で区別することができます。添字の個数を「次元」といいます。

添字の数がひとつの配列を「1 次元配列」といい、特別に「ベクタ (vector)」と呼びます。添字の数が 2 つの配列は「2 次元配列」といいます。これは、数学で習った「行列 (matrix)」を思い出してもらえばいいでしょう。一般に、添字の個数が n 個であれば「n 次元配列」といいます。

たとえば、このマンションは平屋建てでしたが、これを 10 階建てに改築したとしましょう。すると、各部屋は 0 棟 1 階 2 号室というように、3 つの数値で区別することができますね。つまり、3 次元配列と考えることができます。

●ベクタの基本的な操作

さて、話ばかりでは退屈なので、具体的にベクタの使い方を説明しましょう。まずは R7RS-small に規定されているベクタの操作関数から説明します。

ベクタは次の関数で作成します。

make-vector k
make-vector k fill
vector obj1 obj2 ...

引数 k は要素の個数を表します。make-vector は k 個の要素を格納するベクタを作成して返します。引数 fill を指定すると、その値でベクタの各要素を初期化します。fill を省略した場合、各要素の値は未定義です。vector は引数 obj1, obj2, ... を要素とするベクタを作成して返します。関数 list のベクタ版です。

簡単な例を示しましょう。

gosh[r7rs.user]> (make-vector 5)
#(#<undef> #<undef> #<undef> #<undef> #<undef>)
gosh[r7rs.user]> (make-vector 5 0)
#(0 0 0 0 0)
gosh[r7rs.user]> (vector 1 2 3 4 5)
#(1 2 3 4 5)

gosh[r7rs.user]> (define a (vector 1 2 3))
a
gosh[r7rs.user]> a
#(1 2 3)
gosh[r7rs.user]> (vector? a)
#t
gosh[r7rs.user]> (vector? 1)
#f
gosh[r7rs.user]> (vector-length a)
3

Scheme の場合、ベクタは #(...) で表記します。これは read で読み込むことができる形式で、プログラムの中で指定することもできます。ベクタは数や文字列と同じく自己評価フォームです。データ型のチェックは型述語 vector? を使います。ベクタの大きさは関数 vector-length で求めることができます。make-vector で初期値が指定されていない場合、Gauche は各要素を #<undef> で初期化します。

ベクタの要素にアクセスするには vector-ref と vector-set! を使います。

vector-ref vector k
vector-set! vector k obj

vector-ref はベクタ vector の k 番目の要素を返します。vector-set! は vector の k 番目の要素の値を obj に書き換えます。vector-set! の返り値は未定義で、Gauche では #<undef> を返します。なお、添字がベクタの範囲を超えるとエラーになります。

簡単な使用例を示しましょう。

gosh[r7rs.user]> (define a1 (vector 10 20 30))
a1
gosh[r7rs.user]> (vector-ref a1 0)
10
gosh[r7rs.user]> (vector-ref a1 2)
30
gosh[r7rs.user]> (define a2 (make-vector 3 0))
a2
gosh[r7rs.user]> a2
#(0 0 0)
gosh[r7rs.user]> (vector-set! a2 0 10)
#<undef>
gosh[r7rs.user]> a2
#(10 0 0)
gosh[r7rs.user]> (vector-set! a2 2 100)
#<undef>
gosh[r7rs.user]> a2
#(10 0 100)

vector-set! は破壊的な操作であることに注意してください。

ところで、今までの例では整数値をベクタに格納しましたが、Lisp / Scheme のベクタは S 式であればどんなデータでも格納することができます。簡単な例を示しましょう。

gosh[r7rs.user]> (vector 1 'a "abc" '(1 2 3))
#(1 a "abc" (1 2 3))

●ベクタの連結とコピー

関数 vector-append は引数のベクタを連結した新しいベクタを返します。関数 vector-copy は引数のベクタの要素をコピーした新しいベクタを返します。

vector-append vec1 vec2 ...
vector-copy vec [start [end]]

vector-copy は start 番目の要素から end - 1 番目の要素をコピーします。end を省略すると最後まで、start を省略すると、ベクタの要素すべてをコピーします。

簡単な使用例を示しましょう。

gosh[r7rs.user]> (vector-append #(1 2 3) #(4 5 6))
#(1 2 3 4 5 6)
gosh[r7rs.user]> (vector-append #(1 2 3) #(4 5 6) #(7 8 9))
#(1 2 3 4 5 6 7 8 9)
gosh[r7rs.user]> (define a #(1 2 3 4 5 6 7 8))
a
gosh[r7rs.user]> (define b (vector-copy a))
b
gosh[r7rs.user]> b
#(1 2 3 4 5 6 7 8)
gosh[r7rs.user]> (vector-set! b 7 80)
#<undef>
gosh[r7rs.user]> b
#(1 2 3 4 5 6 7 80)
gosh[r7rs.user]> a
#(1 2 3 4 5 6 7 8)
gosh[r7rs.user]> (vector-copy a 1 6)
#(2 3 4 5 6)

●ベクタの破壊的な操作

ベクタを他のベクタで上書きしたい場合は vector-copy! を使います。

vector-copy! dst from src [start [end]]

vector-copy! はベクタ src の start 番目から end - 1 番目の要素を、ベクタ dst の from 番目以降に上書きします。引数 start と end は vector-copy と同じです。vector-copy! の返り値は未定義です。簡単な例を示しましょう。

gosh[r7rs.user]> (define a (make-vector 10 0))
a
gosh[r7rs.user]> a
#(0 0 0 0 0 0 0 0 0 0)
gosh[r7rs.user]> (vector-copy! a 3 #(1 2 3 4))
#<undef>
gosh[r7rs.user]> a
#(0 0 0 1 2 3 4 0 0 0)
gosh[r7rs.user]> (vector-copy! a 0 #(1 2 3 4 5 6 7 8 9 10))
#<undef>
gosh[r7rs.user]> a
#(1 2 3 4 5 6 7 8 9 10)

もうひとつ、破壊的な操作関数を紹介しましょう。

vector-fill! vector obj [start [end]]

vector-fill! はベクタ vector の start 番目から end - 1 番目までの要素を引数 obj に書き換えます。引数 start と end は vector-copy と同じです。

gosh[r7rs.user]> (define a (vector 1 2 3 4 5))
a
gosh[r7rs.user]> a
#(1 2 3 4 5)
gosh[r7rs.user]> (vector-fill! a 0)
#<undef>
gosh[r7rs.user]> a
#(0 0 0 0 0)
gosh[r7rs.user]> (vector-fill! a 1 1 4)
#<undef>
gosh[r7rs.user]> a
#(0 1 1 1 0)

●ベクタの変換

R7RS-small には、リストとベクタ、文字列とベクタの相互変換を行う関数が用意されています。

vector->list vector [start [end]]
list->vector list
vector->string vector [start [end]]
string->vector string

vector->list は引数のベクタの要素を新しいリストに格納して返します。逆に、list->vector は引数のリストの要素を新しいベクタに格納して返します。vector->string は引数のベクタの要素 (文字) を文字列にして返します。string->vector は文字列 string の文字に分解して、それを格納したベクタを返します。

簡単な例を示します。

gosh[r7rs.user]> (define a (vector 1 2 3 4 5))
a
gosh[r7rs.user]> (vector->list a)
(1 2 3 4 5)
gosh[r7rs.user]> (vector->list a 1 4)
(2 3 4)
gosh[r7rs.user]> (define b (list 1 2 3 4 5))
b
gosh[r7rs.user]> (list->vector b)
#(1 2 3 4 5)

gosh[r7rs.user]> (string->vector "abcdefg")
#(#\a #\b #\c #\d #\e #\f #\g)
gosh[r7rs.user]> (vector->string #(#\a #\b #\c #\d #\e #\f #\g))
"abcdefg"
gosh[r7rs.user]> (vector->string #(#\a #\b #\c #\d #\e #\f #\g) 1 5)
"bcde"

●ベクタの高階関数

R7RS-small には次に示す高階関数も用意されています。

vector-map f vec1 vec2 ...
vector-for-each f vec1 vec2 ...

vector-map は map のベクタ版、vector-for-each は for-each のベクタ版です。簡単な使用例を示しましょう。

gosh[r7rs.user]> (vector-map (lambda (x) (* x x)) #(1 2 3 4 5))
#(1 4 9 16 25)
gosh[r7rs.user]> (vector-map (lambda (x y) (cons x y)) #(a b c d e) #(1 2 3 4 5))
#((a . 1) (b . 2) (c . 3) (d . 4) (e . 5))
gosh[r7rs.user]> (vector-for-each (lambda (x) (display x) (newline)) #(a b c d e))
a
b
c
d
e
#<undef>

●do

ところで、ベクタを操作するとき、再帰定義よりも繰り返しのほうが便利な場合があります。ここで Scheme の do について簡単に説明しておきましょう。do の構文は少々複雑です。

(do ((var init-form [step-form]) ...) (end-test [result ...]) Ｓ式 ... )

変数 var を init-form の評価結果に初期化します。
end-test を評価し、結果が真であれば繰り返しを終了します。ここで result を評価します。result は複数の S 式を指定することができ、最後の S 式の評価結果が do の返り値になります。result が省略された場合、Gauche は #t を返します。
本体の S 式を順番に評価します。
変数 var の値を step-form の評価結果に更新します。step-form がない場合は何もしません。
2 から 4 までを繰り返します。

変数 var はレキシカル変数として扱われます。do の処理を図に表すと次のようになります。


              図 : do の処理

ここで Scheme の do は変数 var を更新するときに破壊的な操作は行っていないことに注意してください。つまり、do は名前付き let のように、繰り返しを再帰定義で実現しています。

do はＣ言語の for 文とよく似ています (実際は FORTRAN の do ループの影響を受けたと思われます)。ただし、Ｃ言語では end-test が真の間は繰り返しを続けるのですが、Scheme の do は end-test が真になると繰り返しを終了します。繰り返しを続ける条件が逆になっているので注意して下さい。

それでは簡単な使用例を示しましょう。

リスト : do の使用例

(define (fact x)
  (do ((n 1 (+ n 1)) (result 1))    ; 変数の定義
      ((> n x) result)              ; end-test と result 
    (set! result (* result n))))    ; 繰り返す S 式

do を使って階乗を計算します。1 から x までを順番に乗算します。n と result がレキシカル変数です。変数 n は 1 に初期化されます。そして、繰り返すたびに step-form の (+ n 1) が評価され、n の値がひとつ増えます。result は 1 に初期化されますが、step-form は省略されています。(> n x) が終了条件で、result の評価結果が do の返り値になります。(> n 1) の評価値が真になると、繰り返しを終了して result の値を返します。

●線形探索と畳み込み

それでは簡単な例題として、ベクタ用の高階関数を作ってみましょう。なお、これから作成する関数のほとんどはライブラリ SRFI-43 に用意されています。今回は Scheme のお勉強ということで、実際にプログラムを作ってみましょう。

最初にベクタの中からデータを探索する関数を作ります。いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを「線形探索 (linear searching)」といます。次のリストを見てください。

リスト : データの探索

;;; 見つけたデータを返す
(define (vector-find p vs)
  (do ((k (vector-length vs))
       (i 0 (+ i 1)))
      ((or (>= i k)
           (p (vector-ref vs i)))
       (if (< i k) (vector-ref vs i) #f))))

;;; 見つけたデータの位置を返す
(define (vector-position p vs)
  (do ((k (vector-length vs))
       (i 0 (+ i 1)))
      ((or (>= i k)
           (p (vector-ref vs i)))
       (if (< i k) i #f))))

;;; 述語 p が真となる要素の個数を返す
(define (vector-count p vs)
  (do ((k (vector-length vs))
       (c 0)
       (i 0 (+ i 1)))
      ((>= i k) c)
    (when (p (vector-ref vs i)) (set! c (+ c 1)))))

関数 vector-find はベクタ vs の中から述語 p が真を返す要素を探します。do ループでベクタの要素を先頭から順番に調べていきます。局所変数 i が添字を表します。i がベクタの大きさ以上になる、または述語 p が真を返したならば do ループを終了します。そして、i がベクタの範囲内にあるかチェックします。そうならば、探索成功なので要素を返します。そうでなければ #f を返します。

関数 vector-position は見つけた要素の位置 i を返すだけです。関数 vector-count は述語 p が真となる回数を求めます。回数は局所変数 c でカウントします。c は 0 に初期化し、述語 p が真を返す場合は c を +1 します。

Common Lisp の場合、return を使って do ループから脱出することができますが、Scheme の do ループには return のような簡単な手段 ^[*1] がありませせん。vector-find と vector-position は名前付き let (named-let) を使ったほうがわかりやすいかもしれません。

簡単な実行例を示しましょう。

gosh[r7rs.user]> (define a #(1 2 3 4 5 6 7))
a
gosh[r7rs.user]> (vector-find even? a)
2
gosh[r7rs.user]> (vector-find odd? a)
1
gosh[r7rs.user]> (vector-find (lambda (x) (> x 10)) a)
#f

gosh[r7rs.user]> (define a #(1 2 3 4 5 6 7))
a
gosh[r7rs.user]> (vector-position even? a)
1
gosh[r7rs.user]> (vector-position odd? a)
0
gosh[r7rs.user]> (vector-position (lambda (x) (> x 10)) a)
#f

gosh[r7rs.user]> (vector-count even? a)
3
gosh[r7rs.user]> (vector-count odd? a)
4
gosh[r7rs.user]> (vector-count (lambda (x) (> x 10)) a)
0

このように、線形探索は簡単にプログラムできますが、大きな欠点があります。データ数が多くなると処理に時間がかかるのです。近年、パソコンの性能は著しく向上しているので、線形探索でどうにかなる場合もありますが、データ数が多くて時間かかかるのであれば、例題で取り上げる「二分探索」や他の高速な探索アルゴリズム ^[*2] を使ってみてください。

次は畳み込みを行う関数を作ります。

リスト : 畳み込み

(define (vector-foldl f a vs)
  (do ((i 0 (+ i 1)))
      ((>= i (vector-length vs)) a)
    (set! a (f a (vector-ref vs i)))))

(define (vector-foldr f a vs)
  (do ((i (- (vector-length vs) 1) (- i 1)))
      ((negative? i) a)
    (set! a (f (vector-ref vs i) a))))

関数 vector-foldl はベクタの先頭から、関数 vector-foldr はベクタの最後尾から順番に要素を取り出して畳み込み処理を行います。ベクタは最後尾の要素にも簡単にアクセスできるので、vector-foldr も繰り返しで処理することができます。

それでは簡単な例を示しましょう。

gosh[r7rs.user]> a
#(1 2 3 4 5 6 7)
gosh[r7rs.user]> (vector-foldl + 0 a)
28
gosh[r7rs.user]> (vector-foldr + 0 a)
28
gosh[r7rs.user]> (vector-foldl list 0 a)
(((((((0 1) 2) 3) 4) 5) 6) 7)
gosh[r7rs.user]> (vector-foldr list 8 a)
(1 (2 (3 (4 (5 (6 (7 8)))))))

-- note --------
[*1] Scheme の「継続」という機能を使うとループから脱出することができます。
[*2] 基本的なところでは、「ハッシュ法」や「二分探索木」などがあります。

●二分探索

次は、ベクタの応用例として「二分探索 (バイナリサーチ：binary searching)」を例題として取り上げます。線形探索の実行時間は要素数 N に比例するので、数が多くなると時間がかかるようになります。これに対し二分探索は log₂ N に比例する時間でデータを探すことができます。

ただし、探索するデータはあらかじめ昇順に並べておく必要があります。この操作を「ソート (sort)」といいます。二分探索は最初にデータをソートしておかないといけないので、線形探索に比べて準備に時間がかかります。

二分探索の動作を下図に示します。


                     図 : 二分探索

二分探索は探索する区間を半分に分割しながら調べていきます。キーが 66 の場合を考えてみましょう。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索すればいいのです。

あとは、これと同じことを後半部分に対して行います。最後には区間の要素が一つしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。

上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 1,000,000 個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。

二分探索は要素をランダムアクセスすることになるので、リストには不向きのアルゴリズムです。そこで、ベクタからデータを二分探索するプログラムを作ってみましょう。二分探索は簡単にプログラムできます。次のリストを見てください。

リスト : 二分探索

;;; 比較関数
(define (num-cmp x y) (- x y))

;;; ベクタの二分探索
(define (vector-binary-search item vec cmp)
  (let loop ((low 0)
             (high (- (vector-length vec) 1)))
    (if (> low high)
        #f
        (let* ((mid (quotient (+ low high) 2))
               (r (cmp item (vector-ref vec mid))))
          (cond
           ((zero? r) mid)
           ((> r 0)
            (loop (+ mid 1) high))
           (else
            (loop low (- mid 1))))))))

関数 vector-binary-search はベクタ vec の中から item と等しい要素を二分探索し、見つけた場合はその位置を返します。見つからない場合は #f を返します。item と要素の比較は引数 cmp に渡された比較関数で行います。(cmp x y) は x < y ならば負の値を、x = y ならば 0 を、x > y ならば正の値を返すこととします。数値の場合は関数 num-cmp のように定義すると簡単です。

最初に、探索する区間を示す変数 low と high を初期化します。ベクタの大きさは関数 vector-length で取得し、最後の要素の位置を high にセットします。次に名前付き let の繰り返しで探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて変数 mid にセットします。そして、関数 cmp で item と mid の位置の要素を比較して、その結果を変数 r にセットします。r が 0 の場合は探索成功です。見つけた位置 mid を返します。

r が 0 よりも大きい場合は区間の後半を調べます。変数 low に mid + 1 をセットします。逆に、r が 0 よりも小さい場合は前半を調べるため、変数 high に mid - 1 をセットします。これを二分割できる間繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し #f を返します。

これでプログラムは完成です。簡単な実行例を示しましょう。

gosh[r7rs.user]> (define a (vector 11 22 33 44 55 66 77 88 99))
a
gosh[r7rs.user]> (vector-binary-search 44 a num-cmp)
3
gosh[r7rs.user]> (vector-binary-search 40 a num-cmp)
#f

二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。

●ソート

ソート (sort) は、ある規則に従ってデータを順番に並べ換える操作のことです。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。たいていの Scheme 処理系にはリストやベクタをソートする関数が用意されています。もちろん Gauche にも関数 sort がありますが、私達でもプログラムすることができます。

今回は簡単な例題ということで、挿入ソート (insert sort) を取り上げます。挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。下図を見てください。

   [9] 5 3 7 6 4 8    5 を取り出す

   [9] * 3 7 6 4 8    5 を[9]の中に挿入する

   [5 9] 3 7 6 4 8    9 をひとつずらして先頭に 5 を挿入

   [5 9] * 7 6 4 8    3 を取り出して[5 9]の中に挿入する

   [3 5 9] 7 6 4 8    先頭に 3 を挿入

   [3 5 9] * 6 4 8    7 を取り出して[3 5 9] に挿入

   [3 5 7 9] 6 4 8    9 を動かして 7 を挿入
                      残りの要素も同様に行う


               図 : 挿入ソート

最初は先頭のデータひとつがソート済みと考えて、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。

要素を数値に限定すると、プログラムは次のようになります。

リスト : 挿入ソート

(define (insert-sort vec)
  (do ((i 1 (+ i 1)))
      ((>= i (vector-length vec)) vec)
    (do ((temp (vector-ref vec i))
         (j (- i 1) (- j 1)))
        ((or (negative? j)
             (>= temp (vector-ref vec j)))
         (vector-set! vec (+ j 1) temp))
      (vector-set! vec (+ j 1) (vector-ref vec j)))))

最初の do ループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ (添字では 1) を取り出して挿入していきます。2 番目のループで挿入する位置を探しています。探索は後ろから前に向かって行います。このとき、挿入位置の検索と同時にデータの移動も行っています。ループが最後まで回れば、そのデータは先頭に挿入されることになります。

それでは実行してみましょう。

gosh[r7rs.user]> (insert-sort #(5 6 4 7 3 8 2 9 1 0))
#(0 1 2 3 4 5 6 7 8 9)
gosh[r7rs.user]> (insert-sort #(01 2 3 4 5 6 7 8 9))
#(1 2 3 4 5 6 7 8 9)
gosh[r7rs.user]> (insert-sort #(0 1 2 3 4 5 6 7 8 9))
#(0 1 2 3 4 5 6 7 8 9)
gosh[r7rs.user]> (insert-sort #(9 8 7 6 5 4 3 2 1 0))
#(0 1 2 3 4 5 6 7 8 9)

挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。

●バイトベクタ

R7RS-small には要素をバイト (0 - 255) に限定した「バイトベクタ (bytevector)」が用意されています。バイトベクタは次の関数で作成します。

make-bytevector k
make-bytevector k fill
bytevector obj1 obj2 ...

make-bytevector は make-vector のバイトベクタ版、bytevector は vector のバイトベクタ版です。

簡単な例を示しましょう。

gosh[r7rs.user]> (make-bytevector 10)
#u8(0 0 0 0 0 0 0 0 0 0)
gosh[r7rs.user]> (make-bytevector 10 #xff)
#u8(255 255 255 255 255 255 255 255 255 255)
gosh[r7rs.user]> (bytevector 1 2 3 4 5)
#u8(1 2 3 4 5)
gosh[r7rs.user]> (define a #u8(1 2 3 4 5 6 7 8))
a
gosh[r7rs.user]> (bytevector? a)
#t
gosh[r7rs.user]> (bytevector-length a)
8

バイトベクタは #u8(...) で表記します。これは read で読み込むことができる形式で、プログラムの中で指定することもできます。バイトベクタはベクタと同じく自己評価フォームです。データ型のチェックは型述語 bytevector? を使います。バイトベクタの大きさは関数 bytevector-length で求めることができます。make-bytevector で初期値が指定されていない場合、Gauche は各要素を 0 で初期化します。

バイトベクタの要素にアクセスするには bytevector-u8-ref と bytevector-u8-set! を使います。

bytevector-u8-ref vector k
bytevector-u8-set! vector k obj

これらの関数は vector-ref と vector-set! のバイトベクタ版です。

gosh[r7rs.user]> a
#u8(1 2 3 4 5 6 7 8)
gosh[r7rs.user]> (bytevector-u8-ref a 0)
1
gosh[r7rs.user]> (bytevector-u8-ref a 7)
8
gosh[r7rs.user]> (bytevector-u8-set! a 7 #xff)
#<undef>
gosh[r7rs.user]> a
#u8(1 2 3 4 5 6 7 255)

このほかに、bytevector-append, bytevector-copy, bytevector-copy! などの関数があります。

●バイトベクタを使ったファイルの入出力

バイトベクタはポートの入出力でも使用することができます。

read-bytevector k [iport]
write-bytevector vec [oport [start [end]]]

関数 read-bytevector はバイナリ入力ポートから k 個 (またはファイルの終端まで) のバイトを読み込み、それをバイトベクタに格納して返します。読み込むバイトがない場合は EOF オブジェクトを返します。write-bytevector は引数 vec の start から end - 1 番目の要素をバイナリ出力ポートに書き込みます。

入力データを既存のバイトベクタに読み込みたい場合は次の関数を使います。

read-bytevector! vec [iport [start [end]]]

バイナリ入力ポートからバイトを読み込み、それをバイトベクタ vec の start 番目から end - 1 番目に書き込みます。返り値は読み込んだバイト数です。読み込むバイトがない場合は EOF オブジェクトを返します。

それでは簡単な例題として、Scheme の入出力 [2] で作成したファイルをコピーするプログラム cp.scm をバイトベクタで書き直してみましょう。次のリストを見てください。

リスト : ファイルのコピー

(import (scheme base) (scheme read) (scheme write)
        (scheme file) (scheme process-context))

;;; 1 バイトずつのコピー
(define (cp iport oport)
  (let ((c (read-u8 iport)))
    (unless
     (eof-object? c)
     (write-u8 c oport)
     (cp iport oport))))

;;; バイトベクタを使ったコピー
(define (cp1 iport oport)
  (let ((buff (make-bytevector 256)))
    (do ((n (read-bytevector! buff iport)
            (read-bytevector! buff iport)))
        ((eof-object? n))
      (write-bytevector buff oport 0 n))))

;;; 実行
(let* ((args (command-line))
       (iport (open-binary-input-file  (list-ref args 1)))
       (oport (open-binary-output-file (list-ref args 2))))
  (cp1 iport oport)
  (close-input-port iport)
  (close-output-port oport))

関数 cp1 を見てください。最初に make-bytevector で大きさが 256 のバイトベクタを確保します。これをバッファとして使います。今回は簡単な例題ということで、バッファサイズは 256 と小さな値にしています。次に、do ループでバッファにデータを読み込みます。do ループは初期化と更新処理があるので、それぞれで read-bytevector! を呼び出しています。返り値が EOF オブジェクトであれば do ループを終了します。そうでなければ、write-bytevector で読み込んだデータを出力します。

これでファイルをコピーすることができます。named-let を使ったほうが、もう少し簡単になるかもしれません。興味のある方はプログラムを改良してみてください。

●まとめ

今回はここまでです。簡単に復習しておきましょう。

ベクタは make-vector, vector で作成する。
ベクタの要素にアクセスするには vecto-ref と vector-set! を使う。
ベクタの大きさは vector-length で求める。
ベクタの連結は vector-append で、コピーは vector-copy で行う。
ベクタを破壊的に修正する vector-copy!, vector-fill! もある。
vector->list, list->vector はベクタとリストの変換を行う。
vector->string, string->vector はベクタと文字列の変換を行う。
vector-map と vector-for-each はベクタ用の高階関数である。
do は汎用的な繰り返しを提供する。
二分探索はベクタ向きの高速な探索アルゴリズムである。
データを順番に並べ換える操作をソートという。
バイトベクタは要素をバイト (0 - 255) に限定したベクタである。

次回はリストの破壊的な操作を説明します。

初版 2008 年 1 月 19 日
改訂 2020 年 8 月 30 日

Functional Programming