>>>>> "JCF" == Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> writes:

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

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

Please find below a solution to your problem using this last
solution. In fact this is independant of hash-consing, only tagging
values with unique integers is important. hash-consing can be added if
wanted. I hope my files are self-explanatory, but otherwise please
ask me if you need help. The module Inttagset is a variant of patricia
trees borrowed from JCF. The module Foo is what you are looking for,
and test.ml is a example of use.

    JCF> Hope this helps,

Me too !

-- 
| Claude Marché           | mailto:Claude.Marche@lri.fr |
| LRI - Bât. 490          | http://www.lri.fr/~marche/  |
| Université de Paris-Sud | phoneto: +33 1 69 15 64 85  |
| F-91405 ORSAY Cedex     | faxto: +33 1 69 15 65 86    |