**Next message:**Hendrik Tews: "grammar for class types"**Previous message:**Manuel Fahndrich: "RE: stream pattern [< pat=exp >] and extensions to ordinary patte"**Maybe in reply to:**Andrew Kay: "mutually recursive types and modules"**Next in thread:**Hendrik Tews: "grammar for class types"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

Date: Fri, 14 May 1999 13:11:19 +0200

From: "Francisco Valverde Albacete" <fva@tsc.uc3m.es>

Subject: Re: mutually recursive types and modules

Andrew Kay wrote:

*> 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?
*

I have come across this problem as well in trying to implement heuristic

searches...

As recursive modules are, for the time being, dangerous to type and thus

disallowed, you'll have to make do with:

a) defining both structures at the same time, with the obvious work of

recoding

sets, etc.

b) pass a *polymorphic* set structure to your nodes:

module Node

( Set : (* set signature *) )

=

struct

type 'a set = 'a Set.t (* whatever its name in the Set module *)

type node = {

node_id : int;

mutable edges : node set; (* <- Here's the trick *)

... (other fields)

}

....

end

But BEWARE, this is going to cost you almost always an extra parameter to any

constructor in the Set module, a "compare" function to guarantee a linear

order

that makes the Set implementation efficient, so balance very well this with

the

previous alternative...

Hope this helps,

Fran

PS: I have a polymorphic n-ary tree using the same structure you are trying to

build here in case you want to have a look at it. But I warn you that it is

also

quite gory. F.

**Next message:**Hendrik Tews: "grammar for class types"**Previous message:**Manuel Fahndrich: "RE: stream pattern [< pat=exp >] and extensions to ordinary patte"**Maybe in reply to:**Andrew Kay: "mutually recursive types and modules"**Next in thread:**Hendrik Tews: "grammar for class types"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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