From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA22734 for caml-redistribution; Fri, 14 May 1999 12:55:34 +0200 (MET DST)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA29870 for <caml-list@pauillac.inria.fr>; Wed, 12 May 1999 18:57:06 +0200 (MET DST)
Received: from graphics.lcs.mit.edu (graphics.lcs.mit.edu [18.24.2.30])
	by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id SAA24545
	for <caml-list@inria.fr>; Wed, 12 May 1999 18:57:04 +0200 (MET DST)
Received: from tint.lcs.mit.edu (tint.lcs.mit.edu [18.24.2.55])
	by graphics.lcs.mit.edu (8.9.0/8.9.0) with ESMTP id MAA04880;
	Wed, 12 May 1999 12:55:36 -0400 (EDT)
Received: from localhost (b-db@localhost)
	by tint.lcs.mit.edu (8.9.0/8.9.0) with SMTP id MAA04937;
	Wed, 12 May 1999 12:55:37 -0400 (EDT)
Date: Wed, 12 May 1999 12:55:36 -0400 (EDT)
From: Benoit deBoursetty <b-db@graphics.lcs.mit.edu>
Reply-To: Benoit deBoursetty <b-db@graphics.lcs.mit.edu>
To: Andrew Kay <akay@sharp.co.uk>
cc: caml-list@inria.fr
Subject: Re: mutually recursive types and modules
In-Reply-To: <199905111632.RAA19705@byrd.sle.sharp.co.uk>
Message-ID: <Pine.SGI.3.93.990512121943.4863B-100000@tint.lcs.mit.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: weis

	Hi,

	I have a method that could help solve your problem. The thing is,
the new "functors" feature looks very problematic to we programmers...

	I have slightly modified the set.ml file (normally in your ocaml
libraries directory) and saved it under another name, to accept
polymorphic types.

	Basically the input type signature is no longer

# module type OrderedType =
    sig
      type t
      val compare: t -> t -> int
    end

but

# module type PolyOrderedType =
    sig
      type 'a t
      val compare: 'a t -> 'a t -> int
    end

as this had been previously suggested in this mailing-list (I can't
remember the name of that suggestion, but I'd like to thank him very much)

Then I would declare 

# type 'a node =
    { node_id : int;
      data : 'a
    }

(which in fact you could replace by int * 'a)

The input module for my Make functor is then
# module OrderedNodes =
    struct
      type 'a t = 'a node
      let compare n1 n2 = Pervasives.compare n1.node_id n2.node_id
    end

and finally
module NodeSet = Make(OrderedNodes)

After that, you can put what you want in the 'a...
In your case, you would have to use recursive types :

# type mynode_data = { edge_list : mynode NodeSet.t ; ... }
  and mynode = mynode_data node

Note that the "polymorphic sets" can do what the original O'CaML sets do :
the input module type doesn't have to be really variant. For instance, for
a set over the integers, you would just use

# module OrderedIntegers =
   (struct
      type 'a t = int
      let compare = Pervasives.compare
    end
    : PolyOrderedType)

as an input signature.

You can also do what Caml-light did, which was implementing 'a sets,
systematically compared with Pervasives.compare. That is not available
with the original O'CaML Set.Make functor, but it works with this one.
Here's the corresponding PolyOrderedType that works for any element type,
with lexicographic ordering :

# module LexOrderedType =
    struct
      type 'a t = 'a
      let compare = Pervasives.compare
    end

So, that answers your question, I think. Yet it adds a level in your
typing (you have to go through the "data" field first).

   Benoit de Boursetty

Ecole Polytechnique - X96

Permanent address :
   Benoit.de-Boursetty@polytechnique.org)
Current address :
   b-db@graphics.lcs.mit.edu