[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.4 gauche.collection - コレクションフレームワーク

Module: gauche.collection

このモジュールは、様々なコレクションに対して繰り返し処理を行う総称関数を提供します。 Schemeの規格はmapfor-eachなどの繰り返し手続きを定義しており、 またSRFI-1(srfi-1 - List library参照)は更に数多くの繰り返し手続きを提供しますが、 それらはリストに対してしか動作しません。

このモジュールはオブジェクトシステムのメソッドディスパッチを利用して、 これらの手続きをベクタやハッシュテーブルのような一般のコレクションタイプに対しても 効率良く動作するように拡張します。また、ユーザ定義のクラスにこれらの操作を実装するための 簡単な方法も提供します。今のところ、次のような総称関数が提供されています。

マッピング

fold, fold2, fold3, map, map-to, map-accum, for-each

選択と探索

find, find-min, find-max, find-min&max, filter, filter-to, remove, remove-to, partition, partition-to group-collection

変換

coerce-to

その他

size-of, lazy-size-of

基礎的なイテレータ構築メソッド

call-with-iterator, call-with-builder, with-iterator, with-builder, call-with-iterators.

これらの操作は、コレクションとそのサブクラスである シーケンスに対して動作します。コレクションは、その要素を全て 訪れる方法が用意されているようなオブジェクトの集合です。 シーケンスは、要素間に全順序関係が定義されておりインデックスで要素を取り出すことが できるようなコレクションです。

次にあげるGaucheの組み込みオブジェクトはシーケンスあるいはコレクションとして動作します。

<list>

シーケンス

<vector>

シーケンス

<string>

文字のシーケンス

<hash-table>

コレクション。各要素はキーと値のペア。

<s8vector>, <u8vector>, … <f64vector>

シーケンス。メソッドはsrfi-4モジュール内で定義されます。 srfi-4 - 単一型のベクタ参照。

gauche.sequence - シーケンスフレームワークも参照してください。シーケンス特有のメソッドが 追加されます。

オブジェクトの集合を返すようなメソッド、すなわち mapfilterremoveおよびpartitionは、 リストを返します。対応する“-to”がつくメソッド (map-tofilter-toremove-topartition-to) はコレクションクラスも引数に取り、そのクラスのコレクションを返します。


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.4.1 コレクションに対するマッピング

これらのジェネリックファンクションは標準のマッピング手続きを拡張します。 要素だけでなくそのインデックスも必要な場合はシーケンス上のマップを 参照して下さい。

Generic function: fold proc knil coll coll2 …

fold (他のリスト手続き参照) の自然な拡張です。

コレクションcollの各要素Eiに対して、手続きprocが (proc Ei Ri-1) のように呼ばれます。ここで、 Ri-1i > 0 に対しては (i-1)番目のprocの呼び出しの 結果であり、R0knilです。最後のprocの戻り値を返します。

 
(fold + 0 '#(1 2 3 4)) ⇒ 10
(fold cons '() "abc")  ⇒ (#\c #\b #\a)

collがシーケンスでもある場合、要素はシーケンスの順にprocに渡されます。 そうでなければ繰り返しの順序は未定義です。

註:コレクションに対するfold-rightは提供されません。コレクションでは 要素の順序は定義されないため、意味のあるトラバースをするのには foldだけあれば十分だからです。 しかし、シーケンスに対してはfold-rightが定義されます。 シーケンス上のマップを参照して下さい。

複数のコレクションをfoldに渡すこともできます (但し、その全てがシーケンスで なければあまり意味のある操作では無いでしょう)。 k番目のコレクションのi番目の要素をE(k, i)とするとき、 procは以下のように呼ばれます。

 
(proc E(0,i) E(1,i)E(K-1,i) Ri-1)

異なる型のコレクションを混ぜて扱うことができます。

 
(fold acons '() "abc" '#(1 2 3))
  ⇒ ((#\c 3) (#\b 2) (#\a 1))

;; 二つのベクタの内積を計算
(fold (lambda (a b r) (+ (* a b) r)) 0
      '#(3 5 7) '#(2 4 6))
  ⇒ 68

複数のコレクションが与えられた場合、foldは少なくともひとつのコレクションが 終了した時点で終了します。

Generic function: fold2 proc knil1 knil2 coll coll2 …
Generic function: fold3 proc knil1 knil2 knil3 coll coll2 …

foldと似ていますが、1つではなくそれぞれ2, 3個の状態値を 持ち回ります。状態値はknilNによって初期化されます。 手続きprocはコレクションcollNの各要素値と状態値を 引数として取り、fold2の場合は2個、fold3の場合は3個の 値を返さねばなりません。返された値が次の繰り返しでの状態値として 使われます。最後に返された値がfold2, fold3の戻り値と なります。

 
(fold2 (lambda (elt a b) (values (min elt a) (max elt b)))
       256 0 '#u8(33 12 142 1 74 98 12 5 99))
 ⇒ 1 and 142  ;; find minimum and maximum values

下のmap-accumも参照。

Generic function: map proc coll coll2 …

組み込み手続きmap (リストをたどる手続き参照) を拡張します。 コレクションcollの各要素に手続きprocを適用し、その結果をリストにして 返します。

collがシーケンスでもある場合、要素はシーケンスの順にprocに渡されます。 そうでなければ繰り返しの順序は未定義です。

複数のコレクションが与えられた場合、procは各コレクションからの要素を引数として 呼び出されます。mapはひとつでもコレクションの最後に到達したら終了します。 複数のコレクションを渡すのは、コレクションの全てがシーケンスでないとあまり意味がないでしょう。

 
(map (lambda (x) (* x 2)) '#(1 2 3))
  ⇒ #(2 4 6)

(map char-upcase "abc")
  ⇒ (#\A #\B #\C)

(map + '#(1 2 3) '#(4 5 6))
  ⇒ (5 7 9)

mapは常にリストを返します。別のコレクション型で結果を得たい場合は、 次に示すmap-toを使って下さい。何故(map char-upcase "abc")"ABC"を返さないのか疑問なら、この最後にあるディスカッションを参照してください。

Generic function: map-to class proc coll coll2 …

mapと同じように動作しますが、結果はクラスclassのインスタンスとして返されます。 classはコレクションクラスでなければなりません。 また、ビルダーインタフェースを持っている必要があります (基礎的なイテレータ構築メソッド参照).

 
(map-to <vector> + '#(1 2 3) '#(4 5 6))
  ⇒ #(5 7 9)

(map-to <string> char-upcase "def")
  ⇒ "DEF"

(map-to <vector> char=? "bed" "pet")
  ⇒ #(#f #t #f)
Generic function: map-accum proc seed coll1 coll2 …

状態値を持ち回りながらprocのコレクションの各要素への呼び出しを集めます。 procは次のように呼ばれます。

 
(proc elt1 elt2seed)

ここでelt1 elt2 …は coll1 coll2 …の各要素です。 procは2つの値を返さねばなりません。最初の値がmapのように リストへと集められます。2つ目の値は次のprocの呼び出しのseed として使われます。

いずれかのコレクションの要素を使い切った時点で、map-accumは 2つの値を返します。最初の値はprocの最初の戻り値をリストにしたもの、 2番目の値はprocの最後の呼び出しの2番目の戻り値です。

もし与えられたコレクションがシーケンスであった場合は、 procはシーケンスの順序通りに適用されます。

この手続きはHaskellのmapAccumLと似ています。但し、 procの引数と戻り値の順が逆転していることに注意して下さい。

Generic function: for-each proc coll coll2 …

組み込み手続きfor-each (リストをたどる手続き参照) を拡張します。 コレクションcollの各要素に手続きprocを適用します。 procの結果は捨てられます。for-eachの結果は未定義です。

collがシーケンスでもある場合、要素はシーケンスの順にprocに渡されます。 そうでなければ繰り返しの順序は未定義です。

複数のコレクションが与えられた場合、procは各コレクションからの要素を引数として 呼び出されます。for-eachはひとつでもコレクションの最後に到達したら終了します。 複数のコレクションを渡すのは、コレクションの全てがシーケンスでないとあまり意味がないでしょう。

Generic Function: fold$ proc
Generic Function: fold$ proc knil
Generic Function: map$ proc
Generic Function: for-each$ proc

foldmapfor-eachの部分評価版です。

Discussion: mapがリスト以外に対して適用されたとき、どういう コレクション型を返すべきでしょう。 (map * '#(1 2) '#(3 4)) がベクタを返し、 (map char-upcase "abc") が文字列を返すようにするほうが「自然」でしょうか。

そのようなインタフェースは単純な場合には動作するように思えますが、 一般的な拡張は困難です。文字列とベクタが同時に渡されたらどうします? 更に、コレクションクラスによっては繰り返しインタフェースは持っていても ビルダーインタフェースを持っていない場合があり、結果をそのコレクションクラスとして 返せない場合もあります (データベースレコードのコレクションに対してマップする、 といった用法を考えてみて下さい)。また、Schemeプログラマはmapが リストを返すという事実に慣れ親しんでおり、既存のコードもmapの戻り値を リストを受け取る手続きに渡すことがよく行われています。

そこで、結果の型を明示的に指定するmap-toという別のメソッドを定義しました。 結果の型を渡すのは、CommonLispのmap関数にならっていますが、 Gaucheではクラスメタオブジェクトを渡すようにしたため、メソッドディスパッチを使って 拡張することが容易です。“-to” のつくメソッドは結果のコレクションのクラスを 取るというインタフェースはコレクションフレームワーク中で統一的に使われています。


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.4.2 コレクションからの選択と探索

Generic function: find pred coll

predをコレクションcollの要素に適用してゆきます。predが 真の値を返したらそこで打ち切り、その要素を返します。predが真の値を返す 要素が無かった場合は#fを返します。

collがシーケンスでもある場合、要素はシーケンスの順にprocに渡されます。 そうでなければ繰り返しの順序は未定義です。

 
(find char-upper-case? "abcDe") ⇒ #\D
(find even? '#(1 3 4 6)) ⇒ 4
(find even? '(1 3 5 7))  ⇒ #F
Generic function: find-min coll :key key compare default
Generic function: find-max coll :key key compare default

コレクションcollから最小もしくは最大の要素を探して返します。

コレクションの各要素に対し、1引数の手続きkeyが適用され、 その戻り値が比較対象となります。keyのデフォルトはidentityです。 比較対象の値は2引数の手続きcompareで比較されます。 compareのデフォルトは<です。コレクション中の要素数が 1つ以下の場合はcompareは呼ばれません。

コレクションが空の場合は、defaultで指定した値が返されます。 defaultのデフォルト値は#fです。

 
(find-min '((a . 3) (b . 9) (c . -1) (d . 7)) :key cdr) ⇒ (c . -1)
Generic function: find-min&max coll :key key compare default default-min default-max

find-minfind-maxの動作を同時に行い、 最小と最大の要素をふたつの値として返します。 キーワード引数keycomparedefaultの意味は find-minfind-maxと同じです。 また、default-mindefault-maxを使って 最小要素と最大要素のデフォルト値を別々に指定することもできます。

Generic function: filter pred coll

コレクションcoll中の要素のうち、述語手続きpredが真の値を返したものの リストを返します。コレクションがシーケンスであれば、結果の要素の順序は元のシーケンスの 順序と同じになります。

 
(filter char-upper-case? "Hello, World")
  ⇒ (#\H #\W)
(filter even? '#(1 2 3 4)) ⇒ (2 4)
Generic function: filter-to class pred coll

filterと同じですが、結果のコレクションがclassのインスタンスで 返されます。

 
(filter-to <vector> even? '#(1 2 3 4)) ⇒ #(2 4)
(filter-to <string> char-upper-case? "Hello, World")
  ⇒ "HW"
Generic function: remove pred coll

コレクションcoll中の要素のうち、述語手続きpredが偽の値を返したものの リストを返します。コレクションがシーケンスであれば、結果の要素の順序は元のシーケンスの 順序と同じになります。

 
(remove char-upper-case? "Hello, World")
  ⇒ (#\e #\l #\l #\o #\, #\space #\o #\r #\l #\d)
(remove even? '#(1 2 3 4)) ⇒ (1 3)
Generic function: remove-to class pred coll

removeと同じですが、結果のコレクションがclassのインスタンスで 返されます。

 
(remove-to <vector> even? '#(1 2 3 4)) ⇒ #(1 3)
(remove-to <string> char-upper-case? "Hello, World")
  ⇒ "ello, orld"
Generic function: partition pred coll

filterremoveを同時に行います。 二つのリストを返します。最初のリストはコレクションcollの要素のうち 述語手続きpredが真の値を返したものから構成され、二つ目のリストは そうでない要素から構成されます。

 
(partition char-upper-case? "PuPu")
  ⇒ (#\P #\P) and (#\u #\u)
(partition even? '#(1 2 3 4))
  ⇒ (2 4) and (1 3)
Generic function: partition-to class pred coll

partitionと同じですが、結果がクラスclassのコレクションとして 返されます。

 
(partition-to <string> char-upper-case? "PuPu")
  ⇒ "PP" and "uu"
(partition-to <vector> even? '#(1 2 3 4))
  ⇒ #(2 4) and #(1 3)
Generic function: group-collection coll :key key test

partitionを汎化したものです。coll内の要素を同じキーを 持つ値同士でグループ化し、リストのリストにして返します。 キーの値は要素に手続きkeyを適用することで得られます。keyの デフォルト値はidentityです。collの各要素に対して、 keyは正確に一回だけ呼ばれます。 キーの等価性判定には手続きtestが使われます。デフォルト値はeqv?です。

collがシーケンスである場合、結果の各グループに含まれる要素の順は もとのシーケンス内での順と同じになります。

 
(group-collection '(1 2 3 2 3 1 2 1 2 3 2 3))
  ⇒ ((1 1 1) (2 2 2 2 2) (3 3 3 3))

(group-collection '(1 2 3 2 3 1 2 1 2 3 2 3) :key odd?)
  ⇒ ((1 3 3 1 1 3 3) (2 2 2 2 2))

(group-collection '(("a" 2) ("b" 5) ("c" 1) ("b" 3) ("a" 6))
  :key car :test string=?)
  ⇒ ((("a" 2) ("a" 6)) (("b" 5) ("b" 3)) (("c" 1)))

gauche.sequencegroup-sequenceも参照して下さい (その他のシーケンス上の操作参照)。 隣り合う要素同士でグループ化するものです。


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.4.3 コレクションに対する様々な操作

Generic function: size-of coll

コレクションの要素数を返します。 デフォルトのメソッドは、コレクション中の要素をすべて数え上げるものですが、 あまり効率は良くないでしょう。また、無限個の要素を持つコレクションでは 帰ってきません。多くのコレクションクラスはより効率の良い方法でこのメソッドを定義しています。

Generic function: lazy-size-of coll

コレクションの要素数か、もしくはそれを計算するプロミスを返します。 このメソッドの目的は、要素数の計算が高価な場合にそれを避けることにあります。 しばしば、呼び出し側では最適化のための参考値として要素数が欲しい場合があり、 そういった場合は要素数を計算するために時間を費すのは望ましくありません。 このメソッドを代わりに呼び出して、結果がプロミスであればそれを使わない、 という選択ができます。

Generic function: coerce-to class coll

コレクションcollを、クラスclassのインスタンスである 別のコレクションへと変換します。collがシーケンスであり、 classがシーケンスクラスであれば、元のシーケンスの順序は保存されます。

 
(coerce-to <vector> '(1 2 3 4))
  ⇒ #(1 2 3 4)

(coerce-to <string> '#(#\a #\b #\c))
  ⇒ "abc"

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.4.4 基礎的なイテレータ構築メソッド

ここに挙げるメソッドは、他のコレクションメソッドの基礎となるものです。 メソッドのインタフェースは一般のコードで使われることよりも、 効率良く他の繰り返しメソッドを記述するのに便利なように設計されています。 何故このインタフェースを基礎のメソッドとして選んだかについてはこの章の最後に説明します。

Generic function: call-with-iterator collection proc :key start

基礎となるイテレータ構築メソッドです。このメソッドはコレクションcollection から繰り返しのための二つの手続きを作成し、それらを引数として手続きprocを 呼びます。作られる最初の手続きは終了判定手続きで、引数無しで呼び出され、繰り返しが 終了していれば#tを、まだ要素が残っていれば#fを返します。 作られる二番目の手続きはインクリメント手続きで、呼ばれる度に現在の要素を返し、 内部のポインタを次の要素へと進めます。終了判定手続きが#tを返した後に インクリメント手続きを呼んだ場合の動作は未定義です。

コレクションがシーケンスでもある場合、インクリメント手続きはシーケンスの順番に要素を取り出します。 キーワード引数startが与えられていればイテレーションの範囲は start番目の要素から最後の要素までとなります。シーケンスでないコレクションに 対してはstart引数は意味を持ちません。

call-with-iteratorのメソッド実装は、イテレータのエクステントを そのメソッドのダイナミックスコープ内に限ることを許されます。例えば、 メソッドはprocを呼ぶ前に何らかのリソースを確保し(データベースへのコネクションなど)、 procから戻った後でそれを解放するということができます。

このメソッドは proc が返した値をそのまま返します。

 
(call-with-iterator '(1 2 3 4 5)
  (lambda (end? next)
    (do ((odd-nums 0))
        ((end?) odd-nums)
      (when (odd? (next)) (inc! odd-nums)))))
 ⇒ 3

下に示すwith-iteratorマクロも参照してください。

Macro: with-iterator (collection end? next args …) body …

call-with-iteratorを簡潔に呼び出すマクロです。

 
(with-iterator (coll end? next args …) body …)
 ≡
(call-with-iterator coll
  (lambda (end? next) body …)
   args …)
Function: call-with-iterators collections proc

N-aryのイテレータメソッドを書くのに便利な手続きです。 この手続きはコレクションのリストcollectionsの各コレクションに対して call-with-iteratorを呼び、二つのリストを作ります。最初のリストには 終了判定手続きが順に集められており、二つ目のリストにはインクリメント手続きが 順に集められています。そして、これらのリストを引数としてprocを呼び出します。 procが返した値を返します。

Generic function: call-with-builder collection-class proc :key size

基礎的なビルダー構築メソッドです。ビルダーはコレクションをインクリメンタルに 作成する方法です。コレクションクラスによってはこの手続きを提供しないものもあります。

Collection-classは作成されるコレクションのクラスです。 このメソッドは、追加手続きと結果手続きの二つの手続きを作成し、それらを 引数としてprocを呼びます。追加手続きは一つ引数を取り、それを作成中の コレクションに追加します。結果手続きは引数を取らず、作成されたコレクションを返します。 結果手続きが呼ばれた後で追加手続きを呼んだ場合の動作は未定義です。

作られるコレクションのサイズが分かっている場合、キーワード引数sizeを与える ことができます。コレクションクラスによってはその情報を使って効率的にコレクションを 作成することができます。その情報を単に無視するコレクションクラスもあります。 size個より多くの要素が追加されたり、size個の要素が追加される前に 結果手続きが呼ばれたりした場合の動作は未定義です。

コレクションクラスがシーケンスクラスであった場合、追加手続きは要素を シーケンスの順に追加してゆきます。

コレクションクラスによっては、コレクションオブジェクトの初期化のために 他のキーワード引数を取るかもしれません。

このメソッドはprocが返す値を返します。

 
(call-with-builder <list>
  (lambda (add! get)
    (add! 'a) (add! 'b) (add! 'c) (get)))
 ⇒ (a b c)

(call-with-builder <vector>
  (lambda (add! get)
    (add! 'a) (add! 'b) (add! 'c) (get)))
 ⇒ #(a b c)

下に示すwith-builderマクロも参照してください。

Macro: with-builder (collection add! get args …) body …

call-with-builderを簡潔に呼び出すマクロです。

 
(with-builder (coll add! get args …) body …)
 ≡
(call-with-builder coll
  (lambda (add! get) body …)
  args …)

Discussion: 他のイテレータメソッドは全てこのcall-with-iteratorとcall-with-builderの上に構築可能です。 最低限これらのメソッドを定義すれば、そのクラスはコレクションとして振舞うことができます。 もちろん最適化のために他のイテレータメソッドを定義しても構いませんが。

どの操作を基礎的なメソッドとするかには議論の余地があります。 Gaucheでは、作者がよく見るパターンで最も効率が良くなるように考えて現在のスタイルを 選びました。以下に、他の基礎的なメソッドの可能性を検討します。

fold

foldを最も基礎的なメソッドとして、他のイテレータメソッドをその上に 構築することも可能です。繰り返しの状態はスタックに置かれるので効率良く走ります。 foldを基礎とした繰り返し関数を最適化する方法は良く知られています。 しかし、foldを元にしてジェネレータスタイルのインタフェースを 作成するのは複雑です。また、複数のコレクションに対しての繰り返しを書くのも 面倒です。

CPS

繰り返しの中身の手続きに対し、繰り返しを続けるための継続手続きを渡す方法です。 繰り返しを続けたくなければ、手続きは継続を呼ばすにそのまま戻ります。 Oleg Kiselyovの記事(OLEG2)に指摘されているような、 リソース管理の問題があります。

Iterator object

C++のイテレータやCommon Lispのジェネレータのようなオブジェクトを使う方法です。 ループを書くのは容易ですが、終了判定や要素取り出しの度にメソッドディスパッチが 起こってしまいます。

Series

Common Lispのシリーズはコンパイラがシリーズの使われかたを追跡できれば 非常に効率の良いコードに変換できます。Gaucheのコンパイラはそこまでのデータフロー解析を 行っていません。また、それをやったとしても、コレクションクラスを拡張するための方法が Gaucheのオブジェクトシステムとはうまく調和しません。

Macros

効率を気にするなら、イテレータをマクロで書いてしまう方法もあります (例えばScheme48のiteratorマクロなど)。 効率は良いのですが、拡張するにはマクロを書くことが必要となり、 Gaucheのオブジェクトシステムとうまく調和しません。

現在の実装はイテレータオブジェクトアプローチに近いですが、イテレータオブジェクトを 作る代わりにクロージャを使うことで内部のループでのメソッドディスパッチを 避けています。また、現在のインタフェースはリソース管理の問題を解決しています。


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.4.5 コレクションの実装

コレクションクラスの実装に最低限要求されるものには、以下のものがあります。

これにより、mapfor-eachfindfilterなどの イテレータメソッドが動作するようになります。

建設的なメソッド(例えば、コレクションを作るためのmap-toなど)を 作るためには、メソッドcall-with-builderも実装しなければなりません。 メソッドcall-with-builderは、クラスによりディスパッチされるクラスメソッドの 一種で、インスタンスによりディスパッチされる通常のメソッドとは異なります。 Gaucheでは、これはメタクラスを使うことによって実装できます。 最小限のコードは次のようになります。

 
(define-class <your-collection-meta> (<class>) ())

(define-class <your-collection> (<collection>)
 (...) ;; slots
 :metaclass <your-collection-meta>)

(define-method call-with-iterator
    ((coll <your-collection>) proc . options)
  …
  )

(define-method call-with-builder
     ((coll <your-collection-meta>) proc . options)
  …
  )

パフォーマンスの最適化のために、他のジェネリック関数をオーバロードすることも できます。


[ < ] [ > ]   [ << ] [ Up ] [ >> ]

This document was generated by Shiro Kawai on May 28, 2012 using texi2html 1.82.