Gauche:コレクションの探索

Shiro(2017/05/07 08:38:04 UTC): コレクション中から、条件に合う(述語を満たす)要素を探して何かする、というインタフェースについて。

srfi-1はリストに対するこの操作に2種類のAPIを提供していて、後発のsrfiもほぼそれに準じている。Gaucheはfindを汎用のコレクションに適用可能にしている。

• find PRED COLL: COLLの要素のどれかがPREDを満たした時に、その要素を返す。どれも満たさなければ#fが返る。
• any PRED COLL: COLLの要素のどれかがPREDを満たした時に、そのPREDの戻り値を返す。どれも満たさなければ#fが返る。(コレクションが順序つきの場合、複数のコレクションを取ってそれぞれからの要素をPREDに渡すことも可。srfiはリストについてそうしている。)

どちらも便利でよく使うんだけど、ちと問題点がある。

• srfi-1のfindの仕様には欠陥がある。COLLが#fを要素に含んでいてそれがPREDを満たした場合に、見つからなかったのと区別できない。
  • これは、見つからなかった場合に呼び出される継続をfailure thunkとして渡すことで修正できる。srfi-113のset-find/bag-findはそうなっている。
• anyは、Lispの伝統的なmemberと同じく、「述語として使える名前っぽいけど、真偽値以上の情報を返すので他の用途にも使える」という設計。だから?がつかない。でもanyという名前は(特にeveryと対になってると)すんごく述語っぽいので、例えば「コレクションにあるオブジェクトのうち、スロットfooが#fでないものが(ひとつでも)あればそのスロットの値が知りたい」というような場面で(any (cut ~ <> 'foo) coll) が使える、というのはあんまり直感的でない感じだ。

(find P COLL)は(any (^x (and (P x) x)) COLL)と書けるので、 anyはfindの上位互換と言える。名前の直感性も考慮すると、(find PRED COLL FAILURE) で「PREDを満たす要素があった場合にPREDの戻り値を返す。無ければFAILUREを呼ぶ」とするのが設計としては妥当のように思える。この設計のfindを、区別のためにfind'と仮に呼んでおく。

srfi-125 (intermediate hash tables)は find'を採用した。しかし他のsrfiとの一貫性が無いので、今後どうなるかは未知数である。

find'はまた、複数の順序つきコレクションに拡張しにくいという問題がある。failure引数を先に持ってくるのも妙だし。(srfi-125でこの問題が話題にのぼらなかったのは、hash tableが順序なしコレクションだからだろうけど、一般化を考えれば議論してしかるべきであった)。

何でこんなことを書いてるかというと、Gaucheのdictionaryフレームワークに find的なものがあったらいいかなと思って書き始めた時に、 hash-table-findがanyの動作であることに改めて気づいたから。

ゼロから設計し直すなら、dict-findにfind'のセマンティクスを与えるのが妥当と思うが、 複数の順序つきコレクションに対するanyの需要もあることを考えると、 dict-findは互換性重視でfindのセマンティクス(PREDを満たすキーと値を2つの値として返す)にした方が良さそうだ。

アイディア。(dict-find COLL PRED :optional FAILURE SUCCESS) にして、

• COLL中のkey, valueペアについて(PRED KEY VALUE) が呼ばれる
• それが真の値rを返したら、(SUCCESS KEY VALUE R)が呼ばれてその値が戻り値
• ひとつもPREDが満たされなかったら(FAILURE)が呼ばれる
• SUCCESSのデフォルトは(^[k v r] (values k v))
• FAILUREのデフォルトは(^[] (values #f #f))

これだと、デフォルトでsrfi-146のmapping-findのセマンティクス(引数順は他のdict*に合わせてあるが)。anyの動作にしたければSUCCESSで(^[k v r] r)とすればよい。

要検討

• failureとsuccessの順序。success failureの方が覚えやすいと思うが、 実際にはfailureの方だけ指定することの方が多そうな気がする。そうでもないかな? キーワード引数にして順序を考えないというのもありか。

(dict-seek DICT PRED SUCCESS FAILURE) というのを足してみた。 SUCCESSの引数は(predの結果 key value)。

で、これがあればdict-find (srfi-1 findのセマンティクス) も dict-any も 書ける、と意気込んだのだが、dict-everyでひっかかった。

単純に「全てのk,vペアがPREDを満たすかどうか」という述語と考えるなら述語の意味と 返り値をそれぞれ逆にしてやればいい:

(define (dict-every dict pred)
  (dict-seek dict (complement pred) (^[r k v] #f) (^[] #t)))

ところがsrfi-1のeveryは 「全ての要素がPREDを満たした場合、最後のPREDの値が返り値となる」ので、 それに合わせるならこの定義はまずい。

anyに比べてeveryのこの機能はそれほど実用性があるとは思えないんだけど、srfi-1では anyとの対称性のためにこうしたんだろうなあ。順序つきコレクションならそれでも 最後にPREDに渡される要素は決まってるけど、順序なしコレクションの場合は 何が渡るかわからないからますますこの仕様の意味が薄れる。

とはいえanyがあるならeveryも欲しいしなあ。PREDで直ちに判断するのではなく、一段噛ませるという手はある:

gen   :: key, value -> a
check :: a -> bool
succ  :: a, bool, key, value -> b
fail  :: a -> b

dict-seek::  dict, gen, check, succ, fail -> b 

これだとfindとanyはgenにPREDを、checkにidentityを渡せば良く、everyは

(define (dict-every dict pred)
  (dict-seek dict pred not (^[a b k v] #f) identity))

と書ける。ただ、ちと無理やりな抽象化のようにも見える。

srfi-1 everyのセマンティクスが不要で、述語としてのeveryだけ欲しいなら、anyがあればすぐに書けるのでanyだけでいいような気がしてきた。