プログラミング in OCaml メモ
『プログラミング in OCaml』のファンクターのところは、とてもややこしい。整理してみた。
作成するファンクターの仕様
名前： MakeSet
機能： empty, mem, add, inter, elements
compare: 小さい順
ファンクターの引数となるモジュールには、明示的にその型を指定する必要がある。
（その型 = シグネチャ）
今回は、以下のように指定する。
# module type OrderedType =
sig
type t
val compare : t -> t -> int
end;;
(* module type OrderedType = sig type t val compare : t -> t -> int end *)ファンクターの定義
module ファンクター名 ( 引数名 : シグネチャー式 ) = モジュール式
module ファンクター名 = functor ( 引数名 : シグネチャー式 ) -> モジュール式
例)
# module MakeSet (Order : OrderedType) =
struct
type elt = Order.t
type t = elt list
let empty = []
let rec mem elt = function
[] -> false
| x :: rest ->
let r = Order.compare elt x in
(r = 0) || ((r > 0) && mem elt rest)
let rec add elt = function
[] -> [elt]
| (x :: rest as s) ->
match Order.compare elt x with
0 -> s
| r when r < 0 -> elt :: s
| _ -> x :: (add elt rest)
let rec inter s1 s2 =
match (s1, s2) with
(s1, []) -> []
| ([], s2) -> []
| ((e1 :: rest1 as s1), (e2 :: rest2 as s2)) ->
match Order.compare e1 e2 with
0 -> e1 :: inter rest1 rest2
| r when r < 0 -> inter rest1 s2
| _ -> inter s1 rest2
let rec elements s = s
end;;
(*
module MakeSet :
functor (Order : OrderedType) ->
sig
type elt = Order.t
type t = elt list
val empty : 'a list
val mem : elt -> elt list -> bool
val add : elt -> elt list -> elt list
val inter : elt list -> elt list -> elt list
val elements : 'a -> 'a
end
*)コンパイラの応答の特徴
sig 内の type elt のところに Order.t と、引数であるモジュールの名前が現れている。
「これは、ファンクターが適用されたときに生成されるモジュールのシグネチャが、引数として与えられるストラクチャそのものに依存することを表しています。」
ファンクターをストラクチャに適用する
# module MyIntSet = MakeSet (struct
type t = int
let compare i j = i - j
end);;
module MyIntSet :
sig
type elt = int
type t = elt list
val empty : 'a list
val mem : elt -> elt list -> bool
val add : elt -> elt list -> elt list
val inter : elt list -> elt list -> elt list
val elements : 'a -> 'a
end
# let s1 = MyIntSet.add 2 (MyIntSet.add 1 MyIntSet.empty);;
val s1 : int list = [1; 2]
# MyIntSet.elements s1;;
- : int list = [1; 2]型情報を隠す
標準ライブラリの Set の Make ファンクターで作成した場合は、以下のようになっていて、今作成した MakeSet ファンクターとは違っている。
# let my = IntSet.add 2 (IntSet.add 1 IntSet.empty);;
val my : IntSet.t = <abstr>Set.Make と同じように、型情報を隠す。
そのために、返り値に対して、シグネチャを設定する。
module ファンクター名 ( 引数名 : シグネチャ式1 ) : シグネチャ式2 = モジュール式
以上より、さきほどの MakeSet ファンクターを修正する。
# module MakeSet (Order : OrderedType) :
(* 以下、返り値に対するシグネチャ -- elt list は隠す *)
sig
type elt = Order.t
type t
val empty : t
val mem : elt -> t -> bool
val add : elt -> t -> t
val inter : t -> t -> t
val elements : t -> elt list
end
=
struct
type elt = Order.t
type t = elt list
let empty = []
let rec mem elt = function
[] -> false
| x :: rest ->
let r = Order.compare elt x in
(r = 0) || ((r > 0) && mem elt rest)
let rec add elt = function
[] -> [elt]
| (x :: rest as s) ->
match Order.compare elt x with
0 -> s
| r when r < 0 -> elt :: s
| _ -> x :: (add elt rest)
let rec inter s1 s2 =
match (s1, s2) with
(s1, []) -> []
| ([], s2) -> []
| ((e1 :: rest1 as s1), (e2 :: rest2 as s2)) ->
match Order.compare e1 e2 with
0 -> e1 :: inter rest1 rest2
| r when r < 0 -> inter rest1 s2
| _ -> inter s1 rest2
let rec elements s = s
end;;
module MakeSet :
functor (Order : OrderedType) ->
sig
type elt = Order.t
type t
val empty : t
val mem : elt -> t -> bool
val add : elt -> t -> t
val inter : t -> t -> t
val elements : t -> elt list
endこれで、さきほどと同じように、ストラクチャに MakeSet ファンクターを適用すると、
# module MyIntSet = MakeSet (struct
type t = int
let compare i j = i - j
end)
module MyIntSet :
sig
type elt = int
type t
val empty : t
val mem : elt -> t -> bool
val add : elt -> t -> t
val inter : t -> t -> t
val elements : t -> elt list
end
let s2 = MyIntSet.add 2 (MyIntSet.add 1 MyIntSet.empty);;
(* val s2 : MyIntSet.t = <abstr> *)
MyIntSet.elements s2;;
(* - : int list = [1; 2] *) 次に、この返り値のシグネチャを名前をつけて分離する。
たとえば、今回のシグネチャに対して、SET という名をつけて分離してみる。
# module type SET =
sig
type elt (* <== ここに注意。 type elt = Order.t だった *)
type t
val empty : t
val mem : elt -> t -> bool
val add : elt -> t -> t
val inter : t -> t -> t
val elements : t -> elt list
end;;type elt = Order.t という指定のままだと、Order.t で、unbound module Order というエラーが出る。
だから、ここは、type elt だけにする。
そして、それをファンクターの定義で、返り値のシグネチャを指定するところに記述する。
# module MakeSet (Order : OrderedType) : SET with type elt = Order.t =
struct ^^^^^^^^^^^^^^^^^^^^^^^
type elt = Order.t
type t = elt list
let empty = []
let rec mem elt = function
[] -> false
| x :: rest ->
let r = Order.compare elt x in
(r = 0) || ((r > 0) && mem elt rest)
let rec add elt = function
[] -> [elt]
| (x :: rest as s) ->
match Order.compare elt x with
0 -> s
| r when r < 0 -> elt :: s
| _ -> x :: (add elt rest)
let rec inter s1 s2 =
match (s1, s2) with
(s1, []) -> []
| ([], s2) -> []
| ((e1 :: rest1 as s1), (e2 :: rest2 as s2)) ->
match Order.compare e1 e2 with
0 -> e1 :: inter rest1 rest2
| r when r < 0 -> inter rest1 s2
| _ -> inter s1 rest2
let rec elements s = s
end;;
(* ファンクターのストラクチャへの適用 *)
module MyIntSet = MakeSet (struct
type t = int
let compare i j = i - j
end)
let s3 = MyIntSet.add 2 (MyIntSet.add 1 MyIntSet.empty);;
(* val s2 : MyIntSet.t = <abstr> *)
MyIntSet.elements s3;;
(* - : int list = [1; 2] *) 