mutually recursive types and modules

mutually recursive types and modules

[Andrew Kay]

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

Re: mutually recursive types and modules

[Benoit deBoursetty]

	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

Re: mutually recursive types and modules

[Markus Mottl]

> 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.

Unfortunately, there is no way to do this (yet). You might want to take
a look at the following thread in the archive of the OCAML-mailing-list,
where Xavier Leroy explains the problem:

  http://pauillac.inria.fr/caml/caml-list/0896.html

In my case it was the combination of classes and modules in a recursive
way, which also doesn't work.

There is no short workaround. I solved my problem by redesigning the
system so that it does not require mutual recursive definitions - it's
ok, but not as elegant as it could have been without this restriction.

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: mutually recursive types and modules

[Francisco Valverde Albacete]

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.