Version française
Home     About     Download     Resources     Contact us    
Browse thread
recursive module and types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Christophe Raffalli <christophe.raffalli@u...>
Subject: recursive module and types

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
---------------------------------------------