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

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

Generic function: fold proc knil coll coll2 … ¶

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

コレクションcollの各要素Eiに対して、手続きprocが (proc Ei Ri-1) のように呼ばれます。ここで、 Ri-1 は i > 0 に対しては (i-1)番目のprocの呼び出しの 結果であり、R0はknilです。最後の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 … ¶

{gauche.collection} 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 … ¶

{gauche.collection} 組み込み手続き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 … ¶

{gauche.collection} 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 … ¶

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

(proc elt1 elt2 … seed)

ここで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 … ¶

{gauche.collection} 組み込み手続き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 ¶

{gauche.collection} fold、map、for-eachの部分評価版です。

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

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

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

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

Generic function: find pred coll ¶

{gauche.collection} 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 ¶

{gauche.collection} コレクション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 ¶

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

Generic function: filter pred coll ¶

{gauche.collection} コレクション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 ¶

{gauche.collection} 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 ¶

{gauche.collection} コレクション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 ¶

{gauche.collection} 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 ¶

{gauche.collection} filterとremoveを同時に行います。 二つのリストを返します。最初のリストはコレクション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 ¶

{gauche.collection} 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 ¶

{gauche.collection} 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.sequenceのgroup-sequenceも参照して下さい (その他のシーケンス上の操作参照)。 隣り合う要素同士でグループ化するものです。

Generic function: group-collection->alist coll :key key value test ¶

{gauche.collection} group-collectionに似ていますが、結果を比較に使ったキーでまとめた 連想リストにして返します。例を見るのがわかりやすいでしょう。

(group-collection->alist '((3 "a") (2 "b") (1 "c") (3 "d") (1 "e"))
                         :key car :value cadr)
  ⇒ ((3 "a" "d") (2 "b") (1 "c" "e"))

;; Compare with this
(group-collection '((3 "a") (2 "b") (1 "c") (3 "d") (1 "e"))
                  :key car)
  ⇒ (((3 "a") (3 "d")) ((2 "b")) ((1 "c") (1 "e")))

まず、コレクション中で共通のキーを持つ要素がグループにまとめられます。 次に各グループについて(cons key (map value-proc elements)) が計算され、そのリストが結果となります。ここでvalue-procはキーワード引数 valueで渡した値抽出手続きです。

キーワード引数keyおよびvalueの省略時の値はidentity、 キーの比較に使われるtestの省略時の値はeqv?です。

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

Generic function: size-of coll ¶

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

Generic function: lazy-size-of coll ¶

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

Generic function: coerce-to class coll ¶

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

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

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

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

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

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

{gauche.collection} 基礎となるイテレータ構築メソッドです。このメソッドはコレクション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 … ¶

{gauche.collection} 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 ¶

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

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

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

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 … ¶

{gauche.collection} 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の記事(http://okmij.org/ftp/Scheme/enumerators-callcc.html)に指摘されているような、 リソース管理の問題があります。

Iterator object

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

Series

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

Macros

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

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

9.6.5 コレクションの実装

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

• 抽象クラス<collection>を継承している。
• メソッドcall-with-iteratorが実装されている。

これにより、map、for-each、find、filterなどの イテレータメソッドが動作するようになります。

パフォーマンスの最適化のために、他のジェネリック関数をオーバロードすることも できます。特に、size-ofのメソッドは定義しておくことを強くおすすめします。 デフォルトのメソッドはコレクション全体をなめて大きさを計算するのでO(N)かかりますが、 通常、コレクションは大きさをもっと簡単に得られる手段を持っています。

建設的なメソッド(例えば、コレクションを作るための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)
  …
  )