Re: mutually recursive types and modules

From: Benoit deBoursetty (
Date: Wed May 12 1999 - 18:55:36 MET DST

Date: Wed, 12 May 1999 12:55:36 -0400 (EDT)
From: Benoit deBoursetty <>
To: Andrew Kay <>
Subject: Re: mutually recursive types and modules
In-Reply-To: <>


        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 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 =
      type t
      val compare: t -> t -> int


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

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 =
      type 'a t = 'a node
      let compare n1 n2 = n1.node_id n2.node_id

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 =
      type 'a t = int
      let compare =
    : PolyOrderedType)

as an input signature.

You can also do what Caml-light did, which was implementing 'a sets,
systematically compared with 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 =
      type 'a t = 'a
      let compare =

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 :
Current address :

This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:22 MET