9.31.1 基本的なシーケンスのアクセサ

Method: ref (seq <sequence>) index :optional fallback ¶

{gauche.sequence} シーケンスseqのindex番目の要素を返します。 このメソッドによって、全てのシーケンスが統一的にアクセスできます。

indexが負値だったりシーケンスのサイズ以上だった場合は、 fallbackが与えられていればそれが返され、 そうでなければエラーとなります。

(ref '(a b c) 1)  ⇒ b
(ref '#(a b c) 1) ⇒ b
(ref "abc" 1)     ⇒ #\b

Method: (setter ref) (seq <sequence>) index value ¶

{gauche.sequence} 統一的なシーケンスの変更メソッドです。 シーケンスseqのindex番目の要素にvalueをセットします。

註: シーケンスによってはインデックスによる変更をサポートしていない 場合があります。例えば「ソートされた整数」を表すシーケンスがあった場合、 i番目の要素を適当な整数で置き換えることはできないでしょう。 そのようなシーケンスでも、要素の挿入や削除など、別の方法でシーケンスを 変更する手段が与えられるかもしれません。

(let ((x (list 'a 'b 'c)))
  (set! (ref x 1) 'z)
  x) ⇒ (a z c)

(let ((x (vector 'a 'b 'c)))
  (set! (ref x 1) 'z)
  x) ⇒ #(a z c)

(let ((x (string #\a #\b #\c)))
  (set! (ref x 1) #\z)
  x) ⇒ "azc"

Method: referencer (seq <sequence>) ¶

{gauche.sequence}

Method: modifier (seq <sequence>) ¶

{gauche.sequence}

---

9.31.2 シーケンスのスライス

Method: subseq (seq <sequence>) :optional start end ¶

{gauche.sequence} シーケンスseqの、start番目の要素からend番目の要素の直前 までの部分シーケンスを返します。endが省略された場合はシーケンスの 最後までが取られます。返されるシーケンスの型はseqと同じになります。

(subseq '(a b c d e) 1 4)   ⇒ (b c d)
(subseq '#(a b c d e) 1 4)  ⇒ #(b c d)
(subseq "abcde" 1 4)        ⇒ "bcd"

(subseq '(a b c d e) 3)     ⇒ (d e)

Method: (setter subseq) (seq <sequence>) start end value-seq ¶

Method: (setter subseq) (seq <sequence>) start value-seq ¶

{gauche.sequence} value-seqの各要素を、シーケンスseqのstart番目から end番目の直前まで順にセットします。 value-seqはどんなシーケンスでも構いませんが、 (end - start) よりは長くなくてはなりません。

2番目の形式では、endがvalue-seqの長さから算出されます。

(define s (vector 'a 'b 'c 'd 'e))
(set! (subseq s 1 4) '(4 5 6))
s ⇒ #(a 4 5 6 e)
(set! (subseq s 0)   "ab")
s ⇒ #(#\a #\b 5 6 e)

---

9.31.3 シーケンス上のマップ

シーケンスはまたコレクションでもあるので、シーケンスについて fold、map、for-eachや他のジェネリック関数を 拡張することができます。しかし、時にはイテレーション中に要素そのものと そのインデックスを知りたいことでしょう。そのためのジェネリック関数が いくつかあります。

Method: fold-with-index kons knil (seq <sequence>) … ¶

{gauche.sequence} ジェネリックなfoldと似ていますが、konsにはseqの インデックス内から、第1引数としてseqの要素と増加する値が渡る 点が異なります。

(fold-with-index acons '() '(a b c))
  ⇒ ((2 . c) (1 . b) (0 . a))

Method: map-with-index proc (seq <sequence>) … ¶

Method: map-to-with-index class proc (seq <sequence>) … ¶

Method: for-each-with-index proc (seq <sequence>) … ¶

{gauche.sequence} map、map-to、for-eachと似ていますが、procが 第1引数としてインデックスを受け取る点が違います。

(map-with-index list '(a b c d) '(e f g h))
  ⇒ ((0 a e) (1 b f) (2 c g) (3 d h))

(map-to-with-index <vector> cons '(a b c d))
  ⇒ #((0 . a) (1 . b) (2 . c) (3 . d))

Method: find-with-index pred (seq <sequence>) ¶

{gauche.sequence} findのように、seqの中でpredを満足する最初の要素を 探しますが、2つの値、要素のインデックスと要素自身を返します。 predを満足する要素がなかったら、2つの#fが返ります。

(find-with-index char-upper-case? "abraCadabra")
  ⇒ 4 and #\C

(find-with-index char-numeric? "abraCadabra")
  ⇒ #f and #f

Method: find-index pred (seq <sequence>) ¶

{gauche.sequence} findに似ていますが、seqの中でpredを満足する最初の、 要素自身ではなくインデックスを返す点が異なります。 seqの中にpredを満足する要素がなかったら、#fが返ります。

(find-index char-upper-case? "abraCadabra")
  ⇒ 4

(find-index char-numeric? "abraCadabra")
  ⇒ #f

scheme.list (scheme.list - R7RSリスト参照)のlist-indexも見て下さい。

Method: fold-right kons knil (seq <sequence>) … ¶

{gauche.sequence} リストに対するfold-rightの総称関数版です。 foldと同じように、このメソッドは種となる値 (初期値はknil) を受渡しながら、高階関数konsを与えられたシーケンスの各要素に 適用してゆきます。foldとfold-rightの違いは 要素間の結合の順序にあります。

ひとつだけのシーケンス[E0, E1, ..., En]に適用する場合、 foldとfold-rightはそれぞれ以下のように動作します。

fold:
  (kons En (kons En-1 (kons ... (kons E1 (kons E1 knil)) ...)))

fold-right
  (kons E0 (kons E1 (kons ... (kons En-1 (kons En knil)) ...)))

このメソッドは<collection>に対しては提供されていません。 コレクションは要素の順序を規定しないからです。

---

9.31.4 その他のシーケンス上の操作

選択と検索

Generic function: sequence-contains haystack needle :key test ¶

{gauche.sequence} needleとhaystackはシーケンスです。 haystackの中で、needleに一致するシーケンスを左から探します。 もし見つかれば、haystack中のneedleが始まる場所のインデックスを、 見つからなければ#fを返します。キーワード引数testは 要素を比較するのに使われます。デフォルトはeqv?です。

(sequence-contains '#(a b r a c a d a b r a) '#(b r a))
  ⇒ 1

(sequence-contains '#(a b r a c a d a b r a) '#(c r a))
  ⇒ #f

これは、SRFI-13のstring-containsを一般化したものとみることもできます (文字列の探索参照)。

Function: break-list-by-sequence list needle :key test ¶

Function: break-list-by-sequence! list needle :key test ¶

{gauche.sequence} シーケンスneedleをlistから探し、見つかればlistを needleの直前までとそれ以降に分割して二つの値として返します。 listはリストでなければなりませんが、 needleには任意のシーケンスを渡せます。 各要素はtest手続きで比較されます。デフォルトはeqv?です。

(break-list-by-sequence '(a b r a c a d a b r a) '(c a d))
  ⇒ (a b r a) and (c a d a b r a)

needleがlist中に見つからなかった場合は、 listそのものと()が返されます。 これはspanやbreakの動作に合わせてあります (scheme.list - R7RSリスト参照)。 これらの手続きは要素に対する述語でもってリストを分割しますが、 分割条件が満たされなかった場合はリスト全体を返します。

(break-list-by-sequence '(a b r a c a d a b r c a) '(c a z))
  ⇒ (a b r a c a d a b r c a) and ()

break-list-by-sequence!はその場で更新するバージョンで、 必要ならlistを破壊的に変更して返り値を生成します。渡すリストは変更可能で なければなりません。listが変更されない場合もあるので、 呼出側は副作用に頼らず常に返り値を利用する必要があります。

Function: sequence->kmp-stepper needle :key test ¶

{gauche.sequence} これは、KMPアルゴリズムを使って大きなシーケンス中から 部分シーケンスneedleを探すための内部ルーチンです。 sequence-contains、 break-list-by-sequence、 break-list-by-sequence!の中で使われています。

KMPアルゴリズムの1ステップを行う手続きを返します。 返される手続きは二つの引数、要素eltとインデックスkを取り、 eltと(~ needle k)を比較します。二つの値を返します： 次に比較すべきインデックスと、マッチが終了したかどうかのフラグです。 マッチが終了した場合、次のインデックスとして返される値はneedleの 長さと等しいです。

エッジケースとして、needleが空のシーケンスの場合、 sequence->kmp-stepperは#fを返します。

要素はtestで比較されます。デフォルトはeqv?です。

以下に、sequence->kmp-stepperを使った探索コードの骨格を示します。 この例ではhaystackはリストで、単にneedleが見つかったかどうか (あるいはneedleが空か)だけを返しています。 実際の応用では、他の情報をループで持ち回ることになるでしょう (例えばsequence-containsではhaystack中の インデックスをトラックして、見つかった場所を返しています。)

(if-let1 stepper (sequence->kmp-stepper needle)
  (let loop ([haystack haystack]
             [k 0])
    (if (null? haystack)
      'not-found
      (receive (k found) (stepper (car haystack) k) ; KMP step
        (if found
          'found
          (loop (cdr haystack) k)))))
  'needle-is-empty)

コレクションに対する選択と探索はシーケンスにも使えます。 コレクションからの選択と探索を参照して下さい。

グループ化

Generic function: group-sequence seq :key key test ¶

{gauche.sequence} シーケンスseqの連続する要素で、同じキー値を持つもの同士を グループ化します。 キーの値は要素に手続きkeyを適用することで得られます。keyの デフォルト値はidentityです。sedqの各要素に対して、 keyは正確に一回だけ呼ばれます。 キーの等価性判定には手続きtestが使われます。デフォルト値はeqv?です。

(group-sequence '(1 1 1 2 3 4 4 2 2 3 1 1 3))
  ⇒ ((1 1 1) (2) (3) (4 4) (2 2) (3) (1 1) (3))

(group-sequence '(1 1 1 2 3 4 4 2 2 3 1 1 3)
                :key (cut modulo <> 2)))
  ⇒ ((1 1 1) (2) (3) (4 4 2 2) (3 1 1 3))

(group-sequence '#("a" "a" "b" "b" "c" "d" "d")
                :test string=?)
  ⇒ (("a" "a") ("b" "b") ("c") ("d" "d"))

(group-sequence "aabbcdd"
                :test char=?)
  ⇒ ((#\a #\a) (#\b #\b) (#\c) (#\d #\d))

このメソッドはHaskellのgroupと似ています。 隣り合っていない要素もグループ化したい場合は、 group-collection (コレクションからの選択と探索参照)を使って下さい。

もし、単にそれぞれのグループあたり一つづとつの要素だけを残したい、 つまり、隣り合う重複する要素を除きたい場合は、 下のdelete-neighbor-dupsが使えます。

Generic function: group-contiguous-sequence seq :key key next test squeeze ¶

{gauche.sequence} seq中の連続する要素をまとめます。

(group-contiguous-sequence '(1 2 3 4 7 8 9 11 13 14 16))
  ⇒ ((1 2 3 4) (7 8 9) (11) (13 14) (16))

キーワード引数squeezeに真の値が与えられた場合は、 まとめた後の部分列を、その最初と最後の要素のみに置き換えます。部分列が要素ひとつだけの 場合はそのままです。

(group-contiguous-sequence '(1 2 3 4 7 8 9 11 13 14 16) :squeeze #t)
  ⇒ ((1 4) (7 9) (11) (13 14) (16))

キーワード引数keyはひとつの引数を取る手続きでなければならず、 シーケンスの各要素に一回だけ適用され、その戻り値が結果を作るのに使われます。 デフォルトはidentityです。

キーワード引数nextはひとつの引数を取る手続きでなければならず、 キーの値(key手続きが返すもの)を受け取って、その「次」にあたるキーの値を返します。 デフォルトは(^n (+ n 1))です。

キーワード引数testはふたつの引数を取る手続きでなければならず、 ふたつのキー値が等しいかどうかを判定します。デフォルトはeqv?です。

(group-contiguous-sequence "AbCdFgH"
  :key char-upcase :next (^c (integer->char (+ 1 (char->integer c)))))
  ⇒ ((#\A #\B #\C #\D) (#\F #\G #\H))

Generic function: delete-neighbor-dups seq :key key test start end ¶

{gauche.sequence} seq中で、隣り合う重複する要素を取り除いたものを seqと同じ型のシーケンスとして返します。 seqの型はビルダーを持っていなければなりません。

(delete-neighbor-dups '(1 1 1 2 3 4 4 2 2 3 1 1 3))
  ⇒ (1 2 3 4 2 3 1 3)

(delete-neighbor-dups '#(1 1 1 2 3 4 4 2 2 3 1 1 3))
  ⇒ #(1 2 3 4 2 3 1 3)

(delete-neighbor-dups "1112344223113")
  ⇒ "12342313"

要素同士はデフォルトではeqv?で比較されます。 testキーワード引数に代わりの比較手続きを渡すこともできます。 seq中に要素xとyがこの順で隣り合っているとすると、 比較手続きは常に(test x y)として呼ばれます。 要素が等しかった場合、最初に出現する要素が残ります。

(delete-neighbor-dups "AaaAbBBbCCcc" :test char-ci=?)
  ⇒ "AbC"

keyキーワード引数が与えられた場合、それは1引数の手続きでなければなりません。 seqの各要素に対してその手続きは1回だけ適用され、結果が比較に使われます。

(delete-neighbor-dups
  '((1 . "a") (1 . "b") (2 . "c") (2 . "d"))
  :key car)
  ⇒ ((1 . "a") (2 . "c"))

startとend引数はseqへのインデックスで、 調べる範囲を限定します。start番目の要素から、 end番目の要素の一つ手前までが対象となります。

(delete-neighbor-dups "1112344223113" :start 3 :end 9)
  ⇒ "2342"

Generic function: delete-neighbor-dups! seq :key key test start end ¶

{gauche.sequence} seqを左から右にスキャンし、重複する要素を除いた結果を左に詰めてseqに 格納してゆきます。seqはインデックス指定で変更可能でなければなりません。 つまり、modifierメソッドが定義されてなければなりません。 詰め終わった残りの部分は変更せずに残されます。 最後に変更された場所の次のインデックスを返します。

(let1 v (vector 1 1 2 2 3 3 2 2 4 4)
  (list (delete-neighbor-dups! v)
        v))
  ⇒ (5 #(1 2 3 2 4 3 2 2 4 4))

キーワード引数key、test、start、endの意味は delete-neighbor-dupsと同じです。

(let1 v (vector 1 1 2 2 3 3 2 2 4 4)
  (list (delete-neighbor-dups! v :start 2)
        v))
  ⇒ (6 #(1 1 2 3 2 4 2 2 4 4))

註: このメソッドはmodifierが定義されているシーケンスなら何でも 使えますが、新たなシーケンスをアロケートするdelete-neighbor-dupsより 効率的であるとは限りません。seqがリストや文字列であれば、 一ヶ所の変更にO(n)の時間がかかります(文字列の場合はさらにO(n)のメモリも使います)から トータルのコストはO(n^2)になります。delete-neighbor-dupsなら 時間空間ともにO(n)です。 このメソッドはベクタとその仲間で最も効率よく動作します。 余分なメモリを必要とせず、O(n)時間で済みます。

Generic function: delete-neighbor-dups-squeeze! seq :key key test start end ¶

{gauche.sequence} delete-neighbor-dupsと同じように動作しますが、 seqの格納領域を再利用します。 seq内の重複する要素は消去され、全体の長さが短くなります。 変更後のseqを返します。

シーケンスは長さを変更できるとは限らないので、 このメソッドはそういったシーケンスに対しては定義されません。 gauche.sequenceモジュールでは、 <list>に対してのメソッドだけが提供されます。 リストはset-cdr!を用いることで効率よく中間の要素を削除できます。

(delete-neighbor-dups-squeeze! (list 1 1 1 2 2 2 3 3 3))
  ⇒ (1 2 3)

(delete-neighbor-dups-squeeze! (list 1 1 1 2 2 2 3 3 3 4 4)
                               :start 3 :end 9)
  ⇒ (2 3)

キーワード引数key、test、start、endの意味は delete-neighbor-dupsと同じです。

プレフィクス

Generic function: common-prefix (a <sequence>) (b <sequence>) :key key test ¶

{gauche.sequence} シーケンスaとbに共通するプレフィクスを、aと同じ型の 新たなシーケンスで返します。aとbの型は異なっていても構いません。 aの型はビルダーを持っている必要があります。

aとbのそれぞれ対応する要素について、まずkey手続きが 呼ばれ、その結果がtest手続きで比較されます。省略時にはそれぞれ identityおよびeqv?が使われます。

(common-prefix '(a b c d e) '(a b c e f))
  ⇒ (a b c)

(common-prefix "abcef" '#(#\a #\b #\c #\d #\e))
  ⇒ "abc"

文字列については、SRFI-13に似た機能を持つ手続き string-prefix-lengthがあります。 (文字列のプリフィックスとサフィックス参照)。

Generic function: common-prefix-to (class <class>) (a <sequence>) (b <sequence>) :key key test ¶

{gauche.sequence} シーケンスaとbに共通するプレフィクスを、classの インスタンスとして返します。aとbの型は異なっていても構わず、 ビルダーを持っていなくても構いません。classはビルダーを備えた シーケンスのクラスである必要があります。

キーワード引数についてはcommon-prefixと同じです。

(common-prefix-to <list> "abcde" "ABCEF" :test char-ci=?)
  ⇒ '(#\a #\b #\c)

置換とシャッフル

Generic function: permute (src <sequence>) (permuter <sequence>) :optional fallback ¶

{gauche.sequence} シーケンスsrcの要素をpermuterに従って並べ替えた、新たなシーケンスを 作って返します。返されるシーケンスはsrcと同じ型です。

permuterは正確な整数のシーケンスです。pertmuterのk番目の 要素がiであれば、結果のk番目の要素が(ref src i) になります。従って結果のシーケンスの長さはpermuterと長さと同じになります。 permuterの型はsrcの型と違っていて構いません。

同じインデックスiが複数回permuterに現れても構いません。

(permute '(a b c d) '(3 2 0 1))     ⇒ (d c a b)
(permute '(a b c d) '(0 2))         ⇒ (a c)
(permute '(a b c d) '(0 0 1 1 2 2)) ⇒ (a a b b c c)

permuterの要素の整数がsrcの有効なインデックスの範囲外であった場合、 デフォルトではエラーが通知されます。しかしfallbackが与えられた場合は、 srcの要素の読み出しが(ref src i fallback) として行われます。これは通常、iが範囲外であった場合にfallbackを 返します。

(permute '#(a b c) '(3 2 1 0) 'foo) ⇒ #(foo c b a)

(permute "!,HWdelor" #(2 5 6 6 7 1 -1 3 7 8 6 4 0) #\space)
  ⇒ "Hello, World!"

Generic function: permute-to (class <class>) (src <sequence>) (permuter <sequence>) :optional fallback ¶

{gauche.sequence} 結果のシーケンスがsrcの型でなくclassになること以外は、 permuteと同じです。

(permute-to <string> '(#\a #\b #\c #\d #\r)
            '(0 1 4 0 2 0 3 0 1 4 0))
  ⇒ "abracadabra"

Generic function: permute! (src <sequence>) (permuter <sequence>) :optional fallback ¶

{gauche.sequence} これもpermuteと似ていますが、結果は新たに作られるシーケンスではなく srcを破壊的変更して格納されます。srcは変更可能でなければならず、 またsrcとpermuterは同じ長さでなければなりません。

Generic function: shuffle (src <sequence>) :optional random-source ¶

{gauche.sequence} srcと同じ型、長さのシーケンスで、srcの要素の順序がランダムに 置き換えられたものを返します。

(shuffle '(a b c d e))  ⇒ (e b d c a)
(shuffle "abcde")       ⇒ "bacde"

このジェネリックファンクションはSRFI-27 (srfi.27 - ランダムビットのソース参照) を使っています。デフォルトでは乱数源としてdefault-random-sourceが 使われますが、省略可能引数に乱数源を渡すこともできます。

Generic function: shuffle-to (class <class>) (src <sequence>) :optional random-source ¶

{gauche.sequence} 結果をsrcの型ではなくclassのインスタンスとして返すshuffleです。

Generic function: shuffle! (src <sequence>) :optional random-source ¶

{gauche.sequence} 結果をsrcを破壊的変更して格納するshuffleです。 srcは変更可能でなければなりません。

---

9.31.5 シーケンスを実装する

複数のオブジェクトを順序づけて保持するクラスを定義した場合、 次のシーケンスプロトコルを実装することで、それをシーケンスにすることができます。

<sequence>を継承する: ユーザ定義クラスが<sequence>を継承することにより、 シーケンス関連のメソッドが一様に使えるようになります。なお、<sequence>は <collection>を継承しているので、そのクラスはコレクションにもなります。

コレクションプロトコルを実装する: シーケンスはコレクションでもあるので、 コレクションプロトコルを実装しなければなりません (コレクションの実装)。 少なくともcall-with-iteratorメソッドが必要で、ビルダブルにしたいなら call-with-builderも必要です。 それ以外のコレクションジェネリックファンクションは、 デフォルトメソッドがこれら二つのプリミティブの上に作られているので、 他のメソッドを定義しなくてもコレクションAPIが使えます。 ただ、他のジェネリックファンクションも特定化することで、 ショートカットして性能が見込めるならそうするのが良いでしょう。 特にsize-ofは、デフォルトメソッドは call-with-iteratorで全要素を数え上げるO(N)時間を要するので、 可能なら専用メソッドを定義することを強くおすすめします。

シーケンスプロトコルを実装する: 少なくともreferencerと modifierを実装する必要があります。 シーケンスが変更不可ならmodifierは未定義のままにすることもできます。 デフォルトメソッドはエラーを投げます。 ここでも、性能向上が見込めるなら他のシーケンスAPIを特定化するのが良いでしょう。 可能なら、call-with-reverse-iteratorも定義することをおすすめします。 シーケンスを逆順にたどるAPI (例: fold-right) は、このメソッドが定義されていれば それを使います。定義されていなければ、call-with-iteratorで一旦全要素を 取り出す必要があるのでO(N)空間を消費します。