recursive module and types

recursive module and types

[Christophe Raffalli]

Hello,

I needed to define a (large) recursive type using sets basically as in the example below.
What I do not like is that I need to repeat the definition of the type twice (in my real code the 
type is 100 lines long) ...

Does anyone see a way to avoid it, apart from using parametric types, which is also done below

Cheers,
Christophe

(* data type of finitely branching trees
    with sets for leafs ... *)

module rec T : sig
   type t =
     Node of S.t
   | Leaf

   val compare : t -> t -> int
end = struct
   type t =
     Node of S.t
   | Leaf

   let compare u v = match u, v with
     Leaf, Leaf -> 0
   | Node u', Node v' -> S.compare u' v'
   | Leaf, Node _ -> -1
   | Node _, Leaf -> 1
end

and S : Set.S with type elt = T.t = Set.Make(T)

(* a solution with parametric types
    pb: the parametric type is not
    very readable by itself especially when it will be longer *)

type 'a pre_t  =
     Node of 'a
   | Leaf

module rec T' : sig
   type t = S'.t pre_t

   val compare : t -> t -> int
end = struct
   type t = S'.t pre_t

   let compare u v = match u, v with
     Leaf, Leaf -> 0
   | Node u', Node v' -> S'.compare u' v'
   | Leaf, Node _ -> -1
   | Node _, Leaf -> 1
end
and S' : Set.S with type elt = T'.t = Set.Make(T')

(* The same as a functor to allow storing data in
    the tree *)

module DT (D:Set.OrderedType) = struct
   module rec T : sig
     type t =
       Node of D.t * S.t
     | Leaf

     val compare : t -> t -> int
   end = struct
     type t =
       Node of D.t * S.t
     | Leaf

     let compare u v = match u, v with
       Leaf, Leaf -> 0
     | Node (du,u'), Node (dv,v') ->
	(match D.compare du dv with
	   0 -> S.compare u' v'
	 | c -> c)
     | Leaf, Node _ -> -1
     | Node _, Leaf -> 1
     end

   and S : Set.S with type elt = T.t = Set.Make(T)

end
-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Caml-list] recursive module and types

[Alain Frisch]

On 05/19/2010 02:24 PM, Christophe Raffalli wrote:
> Does anyone see a way to avoid it

I propose:


module rec T : sig
   type t = U.t
   val compare : t -> t -> int
end = struct
   include U

   let compare u v = match u, v with
     Leaf, Leaf -> 0
   | Node u', Node v' -> S.compare u' v'
   | Leaf, Node _ -> -1
   | Node _, Leaf -> 1
end

and S : Set.S with type elt = T.t = Set.Make(T)

and U : sig
   type t =
     Node of S.t
   | Leaf
end = U


The type definition is given only once.


-- Alain