open recursionなモジュールに型定義を持たせる（上）

前回はこちらの記事の内容を非常に簡略化した実装を探ってみた：

blag.bcc32.com

最大の簡略化ポイントはモジュール内でtype t = ...のような型定義がなされないところで、それによっていろいろなところでモジュール間の型の整合性を満たすための制約を明示的に書かないですんだ。

この記事と次の記事（それくらいで終わるといいな・・・）では、そこの部分を少しずつ足していって最終的には上記の記事の内容を全部理解したい。

今回は途中ということで、相互再帰関数を単純なパラメトリック多相にして、親クラスと子クラスで別の型を入れてみる。

こういう感じの再帰関数を：

let rec f (ns : int list) =  if List.length ns > 10 then ns else g (ns @ ns)
and g (ns : int list) =  if List.length ns > 10 then ns else f (ns @ ns @ ns)

'a list -> 'a listにして別々のモジュールで書きたい。

パラメトリック多相なしならこう：

module type MT = sig
  val f : int list -> int list
  val g : int list -> int list
end

module A_ (Self : MT) : MT = struct
  let f ns = if List.length ns > 10 then ns else Self.g (ns @ ns)
  let g ns = ns
end
module rec A : MT = A_(A)

module B_ (Self : MT) : MT = struct
  include A_(Self)
  let g ns = if List.length ns > 10 then ns else Self.f (ns @ ns @ ns)
end
module rec B : MT = B_(B)

でパラメトリック多相を入れるならこんな感じ：

module type MT = sig
  type t
  val f : t list -> t list
  val g : t list -> t list
end

module A_ (Self : MT) : MT with type t = Self.t = struct
  type t = Self.t
  let f (ns : t list)= if List.length ns > 10 then ns else Self.g (ns @ ns)
  let g (ns : t list) = ns
end
module rec A : (MT with type t = int) = A_(
  struct
    type t = int
    include (A : MT with type t := int)
  end)

module B_ (Self : MT) : MT with type t = Self.t = struct
  include A_(Self)
  let g (ns : t list) = if List.length ns > 10 then ns else Self.f (ns @ ns @ ns)
end
module rec B : (MT with type t = float) = B_(
  struct
    type t = float
    include (B : MT with type t := float)
  end)

詳細を個別にみていく。

シグニチャ

シグニチャにtype tを追加して、関数fとgはt list -> t listにする：

module type MT = sig
  type t
  val f : t list -> t list
  val g : t list -> t list
end

ベースクラス

A_ファンクタとA再帰モジュールは、二つ合わせてOOPのベースクラスに相当する。

まずA_ファンクタ：

module A_ (Self : MT) : MT with type t = Self.t = struct
  type t = Self.t
  let f (ns : t list)= if List.length ns > 10 then ns else Self.g (ns @ ns)
  let g (ns : t list) = ns
end

渡されるSelfモジュールのtype tがA_ファンクタの返すモジュールのtype tになる。

module A_ (Self : MT) : MT with type t = Self.tの最後の部分でtがSelf.tであることがモジュールの外からも見えるようにして、その下の行でのモジュール内定義で実際にtype t = Self.tになるようにしている。

A再帰モジュール：

module rec A : (MT with type t = int) = A_(
  struct
    type t = int
    include (A : MT with type t := int)
  end)

ここではA.tはintにすることにした。

A_ファンクタと同じようにmodule rec A : (MT with type t = int)でA.tがintであることをモジュール外からも見えるようにしている。

前回はmodule rec A : MT = A_(A)のような定義だったが、今回はtype t = intという定義を注入する必要が出てくる。

なので：

• module rec A : ... = A_(struct ... include(A ...) end)というようにAをincludeして包む形の無名モジュールを作成している
• その包み込むモジュールでtype t = intと定義している
• include Aのなかでtype tが定義されているとstruct type t = int include A endで二回type tの定義ができることになってしまうのでinclude (A : MT with type t := int)とやってincludeされるモジュールからtype tの定義を消す（:=を使うのはdestructive substitutionというらしい）

この再帰モジュールの定義だけで三回type t =/:= intというコードが出てきて全部微妙に意味が違うので、何が起きているのかを追うのが結構大変。

訂正：module rec A : MT with type t = int = A_(A)で大丈夫だということがわかった。module rec A : MT with type t = intの部分だけで、モジュールの中で明示的に指定しなくてもtype t = intになるようだ。これならdestructive substitutionなどもする必要なし。

子クラス

子クラスの方は、ベースクラスのコードがわかればあまり難しいことはない：

module B_ (Self : MT) : MT with type t = Self.t = struct
  include A_(Self)
  let g (ns : t list) = if List.length ns > 10 then ns else Self.f (ns @ ns @ ns)
end
module rec B : (MT with type t = float) = B_(
  struct
    type t = float
    include (B : MT with type t := float)
  end)

ちょっと複雑なのはB_のなかでtype tを定義せずにinclude A_(Self)の定義をそのまま受け継いでいるポイントくらいか。

ここでは再帰モジュールBを定義するときにtype t = floatにしてみた。

使ってみる

utop # A.f [1;2];;
- : int list = [1; 2; 1; 2]

utop # B.f [1;2];;
Line 1, characters 5-6:
Error: This expression has type int but an expression was expected of type
         float

utop # B.f [1.;2.];;
- : float list = [1.; 2.; 1.; 2.; 1.; 2.; 1.; 2.; 1.; 2.; 1.; 2.]

成功。A.fはint list -> int list、B.fはfloat list -> float listになっている。

ただし記事の冒頭でも書いたとおり、これはfもgも完全にパラメトリック多相、つまりtがなんの型かにまったく依存していないという簡単なケースだ。

ベースクラスと子クラスで、同一ではないレコードのフィールドにアクセスする必要があるようなケースだったらどうだろうか。

というわけで次回はその話。