OCamlでのSetの使い方がよくわからない(どれがいいんでしょう) - ashiato45の日記に引き続き、有限オートマトンをOCamlで記述することを考えます(前の記事は読んでなくても大丈夫です)。今回は文字列を読んで受理拒否を判定する関数は載せず、純粋に有限オートマトンのデータ構造を提供することを考えます。ただし、アルファベットと状態をあらわす値は好きなものを選べるように、ジェネリック的にしたいとしましょう。
2.3 ファンクタなんかを参考にしながら書くとこんな感じになります。
gist.github.com
これで良さそうな気もするのですがここでさらに、ファンクタAutomに具体的によく使う集合を与えて、具体的なオートマトンのモジュールも作ってこのライブラリで提供することを考えましょう。次のように書いてみます。
gist.github.com
今回はZeroとOneを持っているalph型を定義し、その集合をアルファベット集合AlphSetにします。状態集合は文字列集合StringSetということにします。そしてこれらをAutomファンクタに与え、ZeroOneAutomモジュールを作ります(autom_dame2.mliの19行目)。モジュールはシグネチャで制限してインターフェースを提供してやらないことには外部からアクセスできませんので、4行目で定義したファンクタシグネチャAUTOMを使って
module ZeroOneAutom: AUTOM(AlphSet)(StringSet)
と制約することを考えます…が、これはコンパイルエラーになります。文法が定義してあるOCamlの公式マニュアルの
7.10 Module types (module specifications)を見てみると、そもそもこういう書き方はできず、コロンの右側には基本的にはシグネチャを置かなければならないということがわかります。
そこで、仕方がないのでファンクタで帰ってくるものだけを取り出して書き(以下AUTOM')、AUTOMはAUTOM'を返すようにすることを考えてみます。
gist.github.com
ただし、AUTOM'の定義のときには引数のモジュールの情報は使えませんので、とりあえず必要な型だけをast, sst, aset, ssetとして定義しておいて、それを使って全体を定義しておきます(autom_ok.mliの4-15行目)。そして、AUTOMの定義のなかでwith typeを使って、AUTOM'で仮置きした型と、得られたモジュールの型とが一致するという制約をかけます。これで、ZeroOneAtomはAUTOM'シグネチャとtype withを使って無事制限をかけることができました。ついでに、AlphSetとStringSetも外部からきちんとアクセスできるようにtype withで制約をかけてあります。type withのはたらきですが、merlinの表示する情報を見るのがわかりやすい気がします。
module ZeroOneAutom: AUTOM'
with type ast = AlphSet.t
with type sst = StringSet.t
with type aset = AlphSet.Elt.t
with type sset = StringSet.Elt.t
の情報をmerlinで表示させると、次のようになります
sig
type ast = AlphSet.t
type sst = StringSet.t
type sset = StringSet.Elt.t
type aset = AlphSet.Elt.t
type t = {
alph : ast;
states : sst;
trans : sset -> aset -> sset;
init : sset;
final : sst;
}
end
対して、
module ZeroOneAutom: AUTOM'
の情報は
sig
type ast
type sst
type sset
type aset
type t = {
alph : ast;
states : sst;
trans : sset -> aset -> sset;
init : sset;
final : sst;
}
end
となります。このように、type withを使うと、型の後ろにイコールとその型が何かを追加することができるようです。このことを「シグネチャに型の等価性情報を追加する」というようです*1。
ちなみに、先の文法のページ(2.4 ファンクタを使った型の抽象化])を見ていたところ、type withならぬmodule withというのもあるようだったので、これも試してみました。すると、次のようになります。
gist.github.com
「module with M = M2」のようにすることで、AUTOM'シグネチャ内で仮置きしたAlphSetモジュールとStateSetモジュールに(autom_ok2.mliの5、6行目)、モジュールの等価性情報を追加することができています(行18、19や30、31)。実際、
module ZeroOneAutom: AUTOM'
with module AlphSet = AlphSet
with module StateSet = StringSet
の情報をmerlinで見てみると、
sig
module AlphSet :
sig
module Elt :
sig
type t = alph
val t_of_sexp : Ppx_sexp_conv_lib.Sexp.t -> t
val sexp_of_t : t -> Ppx_sexp_conv_lib.Sexp.t
(略)
val sexp_of_t : t -> Base__.Ppx_sexp_conv_lib.Sexp.t
end
module StateSet :
sig
module Elt :
sig
type t = string
val t_of_sexp : Ppx_sexp_conv_lib.Sexp.t -> t
(略)
val sexp_of_t : t -> Base__.Ppx_sexp_conv_lib.Sexp.t
end
type t = {
alph : AlphSet.t;
states : StateSet.t;
trans : StateSet.Elt.t -> AlphSet.Elt.t -> StateSet.Elt.t;
init : StateSet.Elt.t;
final : StateSet.t;
}
end
となっており、確かになかのAlphSetやStateSetにmodule withで与えたAlphSet(これは外側のalph型のためのモジュールの名前！)やStringSetの情報が反映されていることがわかります。
