前々からOCamlのSetの使い方、というかベストプラクティスがよくわからないと思っていたのですが、うまく言葉にできなかったのですがいい例が作れたのでその例にそって「これをどう書くべきなんだろう」というお話をします。
例として考えるのは普通の決定性有限オートマトン(DFA,
決定性有限オートマトン - Wikipedia)です。
DFAのデータを保持できて、かつある文字列(語)を受理するかどうかの判定ができるものを考えます。素朴にlistを使って実装するとこんな感じになります(getのあたりはレコードで書くべきだったかも…):
gist.github.com
ただ、本来はアルファベットや状態は集合であってリストではないので、これを集合を使って書き直したいと思います。
このときありうる実装をとりあえず2つ作ってみたのですが、それぞれ気持ち悪いところがあってどうすればいいのかよくわからないので誰か教えてください…
オートマトンをあらわすファンクタを作って、それにアルファベットや状態の値の型を渡す
gist.github.com
今回はまあいいのですが、状態集合やアルファベット集合はオートマトンとはそもそも別の文脈で作っていて、その集合をオートマトンの状態にしたいなというシナリオのときに、集合を作りはじめる前からMyAutomを作りはじめている(21行目)のが気持ち悪いなという気がしています。
オートマトンをあらわすファンクタを作って、それにアルファベットや状態の値の集合のモジュールを渡す
先の点を解消するために、集合のモジュールはファンクタの外側で作ってしまって、その集合のモジュールをオートマトンをあらわすファンクタに渡すべきでしょうか。まあやっぱり動くのですが、オートマトンの型は値の型に応じて決まってほしくて、その集合に対する操作の仕方まで規定している集合モジュールを取らせるのは気持ち悪くない…?という気がしています。
あるいはそもそもオートマトンの状態をどう持っているかはシグネチャで隠蔽してしまう?
それで外からappend_statesみたいな命令を使って追加していく形にすべきでしょうか。そのほうが疎結合的な意味では衛生的な気もするのですが、そのために手持ちの状態集合をfoldなりで逐一追加して計算コストをかけるのもな…という気がします…
7/30追記
どこまで抽象化したいかとかはユースケースによるので何でもいいんですが、教科書の定義に似せたければ集合を引数にとったほうがいいんじゃないでしょうか。そうすれば集合の実装差し替えられるし。(例えば小さいintの集合はbitmap使った方が早いとか https://t.co/gzKTnSTOHh
— 🐫麒麟🐆 (@camloeba) July 30, 2018
教えていただきました。ありがとうございます。