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 RAA05271 for caml-redistribution; Wed, 12 May 1999 17:51:01 +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 SAA24262 for <caml-list@pauillac.inria.fr>; Tue, 11 May 1999 18:32:25 +0200 (MET DST)
Received: from hades-sle.sharp.co.uk (hades-sle.sharp.co.uk [193.114.241.3])
	by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id SAA24075
	for <caml-list@inria.fr>; Tue, 11 May 1999 18:32:18 +0200 (MET DST)
Received: from sharp.co.uk (inca.sle.sharp.co.uk [192.16.16.3])
	by hades-sle.sharp.co.uk (8.8.8+Sun/8.8.8) with SMTP id RAA06473
	for <caml-list@inria.fr>; Tue, 11 May 1999 17:22:36 +0100 (BST)
Received: from byrd.sle.sharp.co.uk by sharp.co.uk (SMI-8.6/SMI-SVR4)
	id RAA16858; Tue, 11 May 1999 17:29:41 +0100
Received: (from akay@localhost)
	by byrd.sle.sharp.co.uk (8.8.8+Sun/8.8.8) id RAA19705
	for caml-list@inria.fr; Tue, 11 May 1999 17:32:17 +0100 (BST)
Date: Tue, 11 May 1999 17:32:17 +0100 (BST)
From: Andrew Kay <akay@sharp.co.uk>
Message-Id: <199905111632.RAA19705@byrd.sle.sharp.co.uk>
To: caml-list@inria.fr
Subject: mutually recursive types and modules
Sender: weis


Dear OCaml users,

We have a problem with mutually recursive types.

In our project we use a graph representation which could be reduced to:

# type node = { 
#             node_id : int;
#             mutable edges : node list;
#             ... (other fields)
# 	      }

Node_ids are generated at node creation time, and are unique, so we defined:

# type compare_nodes n1 n2 = Pervasive.compare n1.node_id n2.node_id

Then we built sets of nodes:

# module NodeSet = Set.Make(struct type t=node let compare=compare_nodes end)

So far so good.  Next we realised that we don't care about the order of
edges in the edge list, and we are always converting edge lists into sets
to do union operations and so on, so we decided to recode the node type
with edges as sets for efficiency (which is very important here).

* type node = {
*             node_id : int;
*             mutable edges : NodeSet.t;
*             ... (other fields)
* 	      }

At this point the world seemed to spin and make me dizzy, because we can't
defined NodeSet without node, and we can't define node without NodeSet.
I can't see any way to express this in OCaml.

Am I missing something obvious here?  How should I proceed?  Is this kind 
of recursion unreasonable, or just syntactically hard to express in OCaml?
Or am I merely incapable of understanding the manual?

Thanks for any help you can give.

Andrew Kay
Sharp Labs Europe Ltd, Oxford Science Park, Oxford, UK, OX4 4GB
Andrew.Kay@sharp.co.uk  Tel:+44 1865 747711 FAX:+44 1865 747717