David Brown writes:
 > I have a recursive type where I'd like one of the constructors of the
 > type to contain a set of the type (or something like set).  However, I
 > can't figure out how to represent this.
 > 
 > For example:
 > 
 > type foo =
 >   | Integer of int
 >   | String of string
 >   | Set of FooSet
 > 
 > module FooSet = Set.Make (struct type t = foo let compare = compare end)
 > 
 > but this obviously doesn't work.

I'm pretty  sure this has already  been discussed on this  list, but I
couldn't find the related thread in the archives...

A (too) naive solution could be  to make a polymorphic instance of the
Set module (either  by adding an argument 'a  everywhere in signatures
OrderedType  and S,  or  by  copying the  functor  body and  replacing
Ord.compare by compare); then you have polymorphic sets, say 'a Set.t,
balanced using compare, and you can define

	type foo = Integer of int | ... | Set of foo Set.t

Unfortunately this  doesn't work because sets  themselves shouldn't be
compared with  compare, but with  Set.compare (see set.mli).  And then
you  point out  the  main  difficulty: comparing  values  in type  foo
requires  to  be able  to  compare sets  of  foo,  and comparing  sets
requires to *implement* sets and thus to compare values in foo.

Fortunately, there  is another solution  (though a bit  more complex).
First  we  define  a  more  generic  type 'a  foo  where  'a  will  be
substituted later by sets of foo:

	type 'a foo = Integer of int | ... | Set of 'a

Then we implement a variant  of module Set which implements sets given
the following signature:

	module type OrderedType =
	sig
	  type 'a t
	  val compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int
	end

that is where elements are in  the polymorphic type 'a t and where the
comparison function depends on  a comparison function for arguments in
'a (which will represent the  sets, in fine). The functor implements a
type t for  sets using balanced trees, as usual,  and defines the type
of elements elt to be t Ord.t:

	module Make(Ord: OrderedType) =
	  struct
	    type elt = t Ord.t
	    and t = Empty | Node of t * elt * t * int

Right  after, it  implements comparison  over elements  and sets  in a
mutually recursive way:

	let rec compare_elt x y = 
	  Ord.compare compare x y

	and compare = ... (usual comparison of sets, using compare_elt)

The remaining  of the  functor is  exactly the same  as for  Set, with
compare_elt used  instead of Ord.compare. I  attach the implementation
of this module.

There  is (at  least) another  solution: to  use a  set implementation
where comparison  does not require  a comparison of elements.  This is
possible if, for instance, you are performing hash-consing on type foo
(which result  in tagging foo values  with integers, then  used in the
comparison). This  solution is used in Claude  Marché's regexp library
(http://www.lri.fr/~marche/regexp/) and  uses a hash-consing technique
available here: http://www.lri.fr/~filliatr/software.en.html

Hope this helps,
-- 
Jean-Christophe Filliātre (http://www.lri.fr/~filliatr)