#003 代数的データ型

int 型の要素から成るリストは，

type int_list = Nil | Cons of int * int_list

のように再帰的に定義され． 'a t = 'a （ここで type 'a t = Nil | Cons of int * 'a ） を満たすような t の最小不動点として捉えることができる． このような代数的データ型は，以下のように一般化される． まず，次のようなシグニチャを持つモジュールを定義する．

module type F = sig
  type 'a t
  val fmap : ('a -> 'b) -> 'a t -> 'b t
end

型 'a t は上述したものであり， 関数 fmap は構造を保存する写像を表す． このようなモジュールは，以下のファンクタ *1 によって対応する代数的データ型を得ることができる．

module DataType (F : F) = struct
  type mu = In of mu F.t
  let inF x = In x
  let outF (In x) = x
  let rec cata phi x = phi (F.fmap (cata phi) (outF x))
  let rec ana psi x = inF (F.fmap (ana psi) (psi x))
  let rec hylo phi psi x = phi (F.fmap (hylo phi psi) (psi x))
  type build_arg = { run: 'a. ('a F.t -> 'a) -> 'a }
  let build g = g.run inF
end

ただし，ここでは anamorphism・catamorphism・hylomorphism・build もついでに定義している．

たとえば，先ほどの int_list は，以下のように定義できる．

module F_IntList = struct
  type 'a t = Nil | Cons of int * 'a
  let fmap f = function Nil -> Nil | Cons(i,a) -> Cons(i, f a)
end
module IntList = DataType (F_IntList)

厳密には，module F_IntList の後ろに : F のようにモジュールの型を明示する必要があるが， 後で F_IntList.Nil や F_IntList.Cons にアクセスできなくなるため記述していない． F with ...という記法もあるが，ここでは簡単のため単に型を記述しない形式をとっている． この代数データ型の上では，リスト [4;4;1] は，

let nil = IntList.inF F_IntList.Nil
and cons (x,xs) = IntList.inF (F_IntList.Cons(x,xs))

を用いて，cons(4, cons(4, cons(1, nil)))と表現できる． また，リストの要素の総和を求める関数は catamorphism を使って，

let sum = IntList.cata (function
    F_IntList.Nil -> 0
  | F_IntList.Cons(i,a) -> i + a )

と与えることができる．

また，Zero と Succ から成る自然数の型は，

module F_Num = struct
  type 'a t = Zero | Succ of 'a
  let fmap f = function Zero -> Zero | Succ n -> Succ (f n)
end
module Num = DataType (F_Num)

と定義できるし，Tip と Fork から成る二分木の型は，

module F_Bin = struct
  type 'a t = Tip | Fork of 'a * 'a
  let fmap f = function Tip -> Tip | Fork(t1,t2) -> Fork (f t1, f t2)
end
module Bin = DataType (F_Bin)

と定義できる．多相型のリストを定義したい場合は，要素の型を含むモジュールをパラメータとするファンクタとして定義する必要がある．

module ListOf (X : sig type t end) = struct
  type ('elt, 'a) listF = Nil | Cons of 'elt * 'a
  module F_List = struct
    type 'a t = (X.t, 'a) listF
    let fmap f = function Nil -> Nil | Cons(x,a) -> Cons(x, f a)
  end
  include DataType (F_List)
  let nil = inF Nil
  and cons (x,xs) = inF (Cons (x, xs))
end
module StringList = ListOf (struct type t = string end)
module BoolList = ListOf (struct type t = bool end)

---

*1:この「ファンクタ」とは圏論ではなくOCamlでの用語．