For Gauche 0.9.5


Next: , Previous: , Up: ライブラリモジュール - Gauche拡張モジュール   [Contents][Index]

9.28 gauche.sequence - シーケンスフレームワーク

Module: gauche.sequence

シーケンスに関するジェネリックな操作を提供するモジュールです。 シーケンスとは、コレクションのうち要素の順序が規定されているものです。 コレクションの操作全てに加え、シーケンスに対しては、 各要素に整数のインデックスを関連づけること、 それから要素の順序が影響する操作を適用することができます。

このモジュールはgauche.collectionを継承しています (コレクションフレームワーク参照)。 コレクションに使えるジェネリックな操作は全てシーケンスに対しても適用可能です。

Gauche組み込みクラスのうち、リスト、ベクター、そして文字列は シーケンスであり、このモジュールでメソッドが定義されます。 またgauche.uvectorのユニフォームベクタ等、 いくつかの拡張データタイプはシーケンスとなっています。


Next: , Previous: , Up: シーケンスフレームワーク   [Contents][Index]

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

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

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

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

統一的なシーケンスの変更メソッドです。 シーケンスseqindex番目の要素に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>)
Method: modifier (seq <sequence>)

Next: , Previous: , Up: シーケンスフレームワーク   [Contents][Index]

9.28.2 シーケンスのスライス

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

シーケンス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

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

2番目の形式では、endvalue-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)

Next: , Previous: , Up: シーケンスフレームワーク   [Contents][Index]

9.28.3 シーケンス上のマップ

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

Method: fold-with-index kons knil (seq <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>) …

mapmap-tofor-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>)

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>)

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

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

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

SRFI-1 (SRFI-1 リスト操作関数参照)のlist-indexも見て下さい。

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

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

ひとつだけのシーケンス[E0, E1, ..., En]に適用する場合、 foldfold-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>に対しては提供されていません。 コレクションは要素の順序を規定しないからです。


Next: , Previous: , Up: シーケンスフレームワーク   [Contents][Index]

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

Selection and searching

Generic function: sequence-contains haystack needle :key test

needlehaystackはシーケンスです。 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

シーケンスneedlelistから探し、見つかればlistneedleの直前までとそれ以降に分割して二つの値として返します。 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)

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

(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

これは、KMPアルゴリズムを使って大きなシーケンス中から 部分シーケンスneedleを探すための内部ルーチンです。 sequence-containsbreak-list-by-sequencebreak-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 kaystack) k)))))
  'needle-is-empty)

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

Grouping

Generic function: group-sequence seq :key key test

シーケンス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 (コレクションからの選択と探索参照)を使って下さい。

Prefix

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

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

abのそれぞれ対応する要素について、まず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

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

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

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

Permutation and shuffling

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

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

permuterは正確な整数のシーケンスです。pertmuterk番目の 要素が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

結果のシーケンスが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

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

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

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

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

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

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

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

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

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


Previous: , Up: シーケンスフレームワーク   [Contents][Index]

9.28.5 シーケンスを実装する


Previous: , Up: シーケンスフレームワーク   [Contents][Index]