Inter-module dependences

Inter-module dependences

[Damien Bobillot]

Hello,

I'm defining a graph structure compatible with the ocamlgraph library.

I want to be able to access all neighbors and edge to neighbors of a  
vertex in 0(1), so I think I need to store the outgoing edge list of  
each vertex in the vertex structure. I also need to be able to access  
the source and destination of an edge in 0(1), so I store these  
vertex in the edge structure.

A standard Caml will be :

type vertex = {
     label : int;
     out_edges : edge list;
     ...
} and edge = {
     label : int;
     src : vertex;
     dst : vertex;
     ...
}

However, in ocamlgraph, the vertex and edge type must be defined by  
modules of signatures (and I cannot modify it) :

module type VERTEX = sig
     type t
     type label
     val create : label -> t
     val label : t -> label
end
module type EDGE = sig
     type t
     type label
     type vertex
     val create : vertex -> label -> vertex -> t
     val label : t -> label
     val src : t -> vertex
     val dst : t -> vertex
end
module type GRAPH = sig
     module V : VERTEX
     module E : EDGE
     ...
end

Then the graph structure is generally created with a functor like :

module Make_Graph(V : VERTEX)(E : EDGE with type vertex = V.t) = struct
     module V = V
     module E = E
     ...
end

It works fine, but it doesn't respond to my problem : I want that V  
use a type from E and at the same time E use a type of V. So I write  
the following code :

module type MYVERTEX = sig
     include VERTEX
     type edge
     val out_edges : t -> edge list
end

module MyVertex = struct
     type edge
     type t = { label : int; out_edges : edge list }
     let out_edges v = v.out_edges
     ...
end

module MyEdge = struct
     type vertex
     type t = { label : int; src : vertex; dst : vertex }
     ...
end

module Make_MyGraph(V : MYVERTEX with type edge = E.t)(E : EDGE with  
type vertex = V.t) = struct
     module V = V
     module E = E
     ...
end

The compiler found an error on "with type edge = E.t" : "Unbound type  
constructor E.t". I understood it, E has not been defined yet, but I  
want to do that any way : if I suppress "with type edge = E.t", the  
V.edge and E.t types are not the same (and some other functions  
inside Make_MyGraph won't work).

I tried things like :
module Make_MyGraph(VV : MYVERTEX)(EE : EDGE with type vertex = V.t)  
= struct
     module E = EE
     module V = VV with type edge = E.t (*ocamlc doesn't understand  
the with keyword here*)
     ...
end

or
module Make_MyEdge(E : EDGE)(V : MYVERTEX with type edge = E.t) = struct
     include V
end
module Make_MyGraph(VV : MYVERTEX)(EE : EDGE with type vertex = VV.t)  
= struct
     module E = EE
     module V = Make_MyEdge(E)(VV) (*ocamlc doesn't accepte VV,
Modules do not match:
   sig type t = VV.t type label = VV.label type edge = VV.edge end
is not included in
   sig type t type label type edge = E.t end
*)
     ...
end

-- 
Damien Bobillot

Test.ml file :
===================
module type VERTEX = sig
     type t
     type label
end
module type EDGE = sig
     type t
     type label
     type vertex
end
module type MYVERTEX = sig
     include VERTEX
     type edge
end

module MyVertex = struct
     type edge
     type t = { label : int; out_edges : edge list }
end
module MyEdge = struct
     type vertex
     type t = { label : int; src : vertex; dst : vertex }
end
module Make_MyGraph(V : MYVERTEX with type edge = E.t)(E : EDGE with  
type vertex = V.t) = struct
     module V = V
     module E = E
end

(*module Make_MyGraph(VV : MYVERTEX)(EE : EDGE with type vertex =  
V.t) = struct
     module E = EE
     module V = VV with type edge = E.t
end*)

(*module Make_MyEdge(E : EDGE)(V : MYVERTEX with type edge = E.t) =  
struct
     include V
end
module Make_MyGraph(VV : MYVERTEX)(EE : EDGE with type vertex = VV.t)  
= struct
     module E = EE
     module V = Make_MyEdge(E)(VV)
end*)
===========

Re: [Caml-list] Inter-module dependences

[Julien Signoles]

Hello,

> module Make_MyGraph(V : MYVERTEX with type edge = E.t)(E : EDGE with
> type vertex = V.t) = struct
>      module V = V
>      module E = E
>      ...
> end
>
> The compiler found an error on "with type edge = E.t" : "Unbound type
> constructor E.t".

Remember: equality is commutative... You should write:

module Make_MyGraph
  (V: MYVERTEX)
  (E: EDGE with type t = V.edge and type vertex = V.t) =
struct
  ...
end

Hope this helps,
Julien
-- 
mailto:Julien.Signoles@lri.fr ; http://www.lri.fr/~signoles
"In theory, practice and theory are the same,
but in practice they are different" (Larry McVoy)

Re: [Caml-list] Inter-module dependences [solved]

[Damien Bobillot]

[-- Attachment #1: Type: text/plain, Size: 2153 bytes --]


Le 15 juin 05 à 17:39, Remi Vanicat a écrit :

> 2005/6/15, Damien Bobillot <damien.bobillot@m4x.org>:
>
>> I'm defining a graph structure compatible with the ocamlgraph  
>> library.
>>
>> I want to be able to access all neighbors and edge to neighbors of a
>> vertex in 0(1), so I think I need to store the outgoing edge list of
>> each vertex in the vertex structure. I also need to be able to access
>> the source and destination of an edge in 0(1), so I store these
>> vertex in the edge structure.
>>
>> A standard Caml will be :
>>
>> type vertex = {
>>      label : int;
>>      out_edges : edge list;
>>      ...
>> } and edge = {
>>      label : int;
>>      src : vertex;
>>      dst : vertex;
>>      ...
>> }
>>
>> However, in ocamlgraph, the vertex and edge type must be defined by
>> modules of signatures (and I cannot modify it) :
>>
>> module type VERTEX = sig
>>      type t
>>      type label
>>      val create : label -> t
>>      val label : t -> label
>> end
>> module type EDGE = sig
>>      type t
>>      type label
>>      type vertex
>>      val create : vertex -> label -> vertex -> t
>>      val label : t -> label
>>      val src : t -> vertex
>>      val dst : t -> vertex
>> end
>>
>
> [...]
>
>
>> It works fine, but it doesn't respond to my problem : I want that V
>> use a type from E and at the same time E use a type of V.
>
> Why don't you do something like what follow ?
>
> type vertex = {
>       label : int;
>       out_edges : edge list;
>       ...
>  } and edge = {
>       label : int;
>       src : vertex;
>       dst : vertex;
>       ...
>  }
>
> module MyVertex : (VERTEX with t=vertex and label=int)=
> struct
>   type t=vertex
>    ....
> end
>
> module MyEdge : (EDGE with t=edge ...) =
> struct
>   type t = edge
>   ....
> end
>
> It should work with no problem.

Yes, it works !!!

Modules are powerful, but as every powerful things, it's hard to use  
without a manual... (and I didn't found a good manual on the web, if  
you know one I'll be interested).

Thank you very much

-- 
Damien Bobillot


[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2375 bytes --]

Re: [Caml-list] Inter-module dependences

[Damien Bobillot]

[-- Attachment #1: Type: text/plain, Size: 606 bytes --]


Le 15 juin 05 à 17:01, Julien Signoles a écrit :

> Hello,
>
>> module Make_MyGraph(V : MYVERTEX with type edge = E.t)(E : EDGE with
>> type vertex = V.t) = struct
>>      module V = V
>>      module E = E
>>      ...
>> end
>>
>> The compiler found an error on "with type edge = E.t" : "Unbound type
>> constructor E.t".
>>
>
> Remember: equality is commutative... You should write:

 From this point of view, it's obvious... ;)

> module Make_MyGraph
>   (V: MYVERTEX)
>   (E: EDGE with type t = V.edge and type vertex = V.t) =
> struct
>   ...
> end

-- 
Damien Bobillot


[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2375 bytes --]