Gauche:コレクションの探索

Gauche:コレクションの探索

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

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

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

(find P COLL)(any (^x (and (P x) x)) COLL)と書けるので、 anyfindの上位互換と言える。名前の直感性も考慮すると、(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-findfind'のセマンティクスを与えるのが妥当と思うが、 複数の順序つきコレクションに対するanyの需要もあることを考えると、 dict-findは互換性重視でfindのセマンティクス(PREDを満たすキーと値を2つの値として返す)にした方が良さそうだ。


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

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

要検討


(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だけでいいような気がしてきた。


Last modified : 2017/05/11 23:44:30 UTC