a question about recursiv type defintions and functors like Set.Make?

[Phillip Heidegger <heidegger@informatik.uni-freiburg.de>]

Hi,


I have a question about using the set functor. I need a type
like:

CODE1:
type a = BaseCase of string
      | BSet of b set
      | ASet of a set
and  b = BaseCaseB of string
      | ASetB of a set


In my first implementation I used instead of sets lists
and write some functions to manipulate the values of type
a and b. But now I need a faster representation for the sets,
and I try to use the module "Set". But I didn't find a way
using it because of the recursion in the type definition.

I would like to write something like:

CODE2:
type a = BaseCase of string        | BSet of BSet.t
      | ASet of ASet.t
and  b = BaseCaseB of string
      | ASetB of ASet.t
and module ASet = Set.Make(struct type a let compare x y = ...end)
and module BSet = Set.Make(struct type b let compare x y = ...end)
(of cause this is not valid OCaml Code, but I hope it helps to
understand, what I would like to do).

This code did not work because I used the type ASet.t in the
definition of a, and the type a in the functor call of ASet.
Because modules are not recursive in OCaml, I'm not able to
write code like this I think.


Now my next approach was not to use the Set module, but change
the code of this module, so I get a module with polymorph
signature:

CODE3:
module Set :
 sig
   type 'a t
   val empty : 'a t
   val is_empty : 'a t -> bool
   val mem : ('a -> 'a -> int) -> 'a -> 'a t -> bool
   .... (* nearly all functions need a method compare like mem *)
 end


I can write my type as I desired in CODE1, but I have to pass to
all functions, every time I used the set, the compare Function as
a parameter. For example:

if (mem cmpTypeA element aSet) then ......


Is there a better way to implement this set Module? Is there a
way to use the Set functor code?
Is there a way to get recursiv moduls in OCaml? How should I solve
my problem, if I have recursive modules. If it's possible to solve
my problem without using recursive modules, what should I do?


greetings,
Phillip