This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

recursive module and types
• Christophe Raffalli
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Christophe Raffalli 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
---------------------------------------------

```