Re: mutually recursive types and modules

From: Benoit deBoursetty (b-db@graphics.lcs.mit.edu)
Date: Wed May 12 1999 - 18:55:36 MET DST


Date: Wed, 12 May 1999 12:55:36 -0400 (EDT)
From: Benoit deBoursetty <b-db@graphics.lcs.mit.edu>
To: Andrew Kay <akay@sharp.co.uk>
Subject: Re: mutually recursive types and modules
In-Reply-To: <199905111632.RAA19705@byrd.sle.sharp.co.uk>

        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



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