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

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

[Phillip Heidegger]

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

Re: [Caml-list] a question about recursiv type defintions and functors like Set.Make?

[Jon Harrop]

On Monday 21 May 2007 16:01:52 Phillip Heidegger wrote:
> I have a question about using the set functor.

This is a FAQ. From a post of mine (on 1st May 2007) on the OCaml beginners 
list:

Use mutually recursive modules:

# module rec Tree : sig
    type t = Content of int * TreeSet.t
    val compare : t -> t -> int
  end = struct
    type t = Content of int * TreeSet.t
    let compare = compare
  end
  and TreeSet : Set.S = Set.Make(Tree);;
sig type t = Content of int * TreeSet.t val compare : t -> t -> int end
and TreeSet : Set.S

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?e

Re: [Caml-list] a question about recursiv type defintions and functors like Set.Make?

[Phillip Heidegger]

Jon Harrop wrote:
> On Monday 21 May 2007 16:01:52 Phillip Heidegger wrote:
>   
>> I have a question about using the set functor.
>>     
>
> This is a FAQ. From a post of mine (on 1st May 2007) on the OCaml beginners 
> list: [...]

Sorry, I don't know that it's an FAQ. Thanks for help, next time I spend
more time searching the FAQ ;)

Phillip