プログラミング 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] *)