From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id EEBF4BCAF for ; Wed, 15 Jun 2005 14:19:29 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j5FCJSkO027286 for ; Wed, 15 Jun 2005 14:19:28 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA26210 for ; Wed, 15 Jun 2005 14:19:28 +0200 (MET DST) Received: from mx1.polytechnique.org (mx1.polytechnique.org [129.104.30.34]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j5FCJQAX013127 for ; Wed, 15 Jun 2005 14:19:26 +0200 Received: from [192.168.0.11] (falcal.net [81.56.73.55]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ssl.polytechnique.org (Postfix) with ESMTP id 7AA5133172; Wed, 15 Jun 2005 14:19:24 +0200 (CEST) Mime-Version: 1.0 (Apple Message framework v730) Message-Id: Content-Type: multipart/signed; micalg=sha1; boundary=Apple-Mail-3-944324957; protocol="application/pkcs7-signature" To: caml-list@inria.fr Subject: Inter-module dependences From: Damien Bobillot Date: Wed, 15 Jun 2005 14:19:21 +0200 X-Mailer: Apple Mail (2.730) X-Virus-Scanned: by amavisd-new-20030616-p10 at Polytechnique.org X-DCC--Metrics: djali 32702; Body=1 Fuz1=1 Fuz2=1 X-Org-Mail: damien.bobillot.2002@polytechnique.org X-j-chkmail-Score: MSGID : 42B01CD0.000 on nez-perce : j-chkmail score : X : 0/20 1 X-j-chkmail-Score: MSGID : 42B01CCE.000 on concorde : j-chkmail score : X : 0/20 1 X-Miltered: at nez-perce with ID 42B01CD0.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42B01CCE.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; dependences:01 damien:01 damien:01 flowed:01 sig:01 val:01 val:01 sig:01 functor:01 struct:01 struct:01 compiler:01 ocamlc:01 ocamlc:01 functor:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.2 required=5.0 tests=HTML_90_100,HTML_MESSAGE autolearn=disabled version=3.0.2 X-Spam-Level: --Apple-Mail-3-944324957 Content-Type: multipart/alternative; boundary=Apple-Mail-2-944324183 --Apple-Mail-2-944324183 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed 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*) =========== --Apple-Mail-2-944324183 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=ISO-8859-1 Hello,

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

I want to be able to access = all=A0neighbors and edge to=A0neighbors 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=A0standard Caml will be = :

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

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

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

Then the graph structure = is=A0generally created with a functor like :

module Make_Graph(V : = VERTEX)(E : EDGE with = type vertex =3D V.t) =3D= struct
=A0 =A0 module V =3D V
=A0 =A0 module E =3D E
=A0 =A0 ...
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.=A0So I write the following code = :

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

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

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

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


The compiler found an error on = "with type edge =3D 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 =3D E.t", the V.edge and E.t types are not the = same (and some other functions inside=A0Make_MyGraph won't work).


I tried things like :

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


or=A0

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


--=A0

=

Damien Bobillot


Test.ml file :

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

module type = VERTEX =3D sig
=A0= =A0 type = t
=A0 =A0 = type = label
end
module = type EDGE =3D = sig
=A0 =A0 type = t
=A0 =A0 = type = label
=A0 =A0 = type = vertex
end
module = type MYVERTEX =3D = sig
=A0 =A0 include VERTEX
=A0 =A0 type = edge
end

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

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

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

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<= /P>


= --Apple-Mail-2-944324183-- --Apple-Mail-3-944324957 Content-Transfer-Encoding: base64 Content-Type: application/pkcs7-signature; name=smime.p7s Content-Disposition: attachment; filename=smime.p7s MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIGIjCCAtsw ggJEoAMCAQICAw54xzANBgkqhkiG9w0BAQQFADBiMQswCQYDVQQGEwJaQTElMCMGA1UEChMcVGhh d3RlIENvbnN1bHRpbmcgKFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhhd3RlIFBlcnNvbmFsIEZyZWVt YWlsIElzc3VpbmcgQ0EwHhcNMDUwNDEzMTc1MTAxWhcNMDYwNDEzMTc1MTAxWjBJMR8wHQYDVQQD ExZUaGF3dGUgRnJlZW1haWwgTWVtYmVyMSYwJAYJKoZIhvcNAQkBFhdkYW1pZW4uYm9iaWxsb3RA bTR4Lm9yZzCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBAJ1TOYBqwJ42s0Fzz56jY1p0 fplGyikFgoNEUKGnOpqt4vpeoqUppAnORt2yvdQJxfIkhsWkrD/diiPS7MTF73wcxlSJtqYzVzPK G/2WDm6dBinuWCIyWYFhtGedyxbap3kJW44H7cL7HUVVxZ0JhOIOTsjCoEzaeKnML7bctbIJeXEE lErfbDv2jA1PDG1ru5dx+Q+AmbexX92ygnntE6aX3QZLSbhrytg4yCRdV8cOyQ9eFruZBI42RJv3 nJXevjUOr4n+y/7bzijAJj4BFyUU+dllvj6bmk5brnUXheCSOD0Ci20dqGNC1MyJ43b6MoIrbW7j JwYIv12D6KuWoaUCAwEAAaM0MDIwIgYDVR0RBBswGYEXZGFtaWVuLmJvYmlsbG90QG00eC5vcmcw DAYDVR0TAQH/BAIwADANBgkqhkiG9w0BAQQFAAOBgQB0u5b6wgwsbcyzDHJTzshlCn4gshxWtU/1 mH77gBCpsY8L554YV4/Tvm1PzmDzErm++drQf5HMy8sEFjmwLvNfBP0BqtkSqsdRFGR4wHzTjMhS EW5LgmlaccqBQzqQrANtzglgBVbtmBDAV92qHjQslwHK4FohCRRzGl4DLQmqBDCCAz8wggKooAMC AQICAQ0wDQYJKoZIhvcNAQEFBQAwgdExCzAJBgNVBAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJuIENh cGUxEjAQBgNVBAcTCUNhcGUgVG93bjEaMBgGA1UEChMRVGhhd3RlIENvbnN1bHRpbmcxKDAmBgNV BAsTH0NlcnRpZmljYXRpb24gU2VydmljZXMgRGl2aXNpb24xJDAiBgNVBAMTG1RoYXd0ZSBQZXJz b25hbCBGcmVlbWFpbCBDQTErMCkGCSqGSIb3DQEJARYccGVyc29uYWwtZnJlZW1haWxAdGhhd3Rl LmNvbTAeFw0wMzA3MTcwMDAwMDBaFw0xMzA3MTYyMzU5NTlaMGIxCzAJBgNVBAYTAlpBMSUwIwYD VQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29u YWwgRnJlZW1haWwgSXNzdWluZyBDQTCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEAxKY8VXNV +065yplaHmjAdQRwnd/p/6Me7L3N9VvyGna9fww6YfK/Uc4B1OVQCjDXAmNaLIkVcI7dyfArhVqq P3FWy688Cwfn8R+RNiQqE88r1fOCdz0Dviv+uxg+B79AgAJk16emu59l0cUqVIUPSAR/p7bRPGEE QB5kGXJgt/sCAwEAAaOBlDCBkTASBgNVHRMBAf8ECDAGAQH/AgEAMEMGA1UdHwQ8MDowOKA2oDSG Mmh0dHA6Ly9jcmwudGhhd3RlLmNvbS9UaGF3dGVQZXJzb25hbEZyZWVtYWlsQ0EuY3JsMAsGA1Ud DwQEAwIBBjApBgNVHREEIjAgpB4wHDEaMBgGA1UEAxMRUHJpdmF0ZUxhYmVsMi0xMzgwDQYJKoZI hvcNAQEFBQADgYEASIzRUIPqCy7MDaNmrGcPf6+svsIXoUOWlJ1/TCG4+DYfqi2fNi/A9BxQIJNw PP2t4WFiw9k6GX6EsZkbAMUaC4J0niVQlGLH2ydxVyWN3amcOY6MIE9lX5Xa9/eH1sYITq726jTl EBpbNU1341YheILcIRk13iSx0x1G/11fZU8xggLnMIIC4wIBATBpMGIxCzAJBgNVBAYTAlpBMSUw IwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVy c29uYWwgRnJlZW1haWwgSXNzdWluZyBDQQIDDnjHMAkGBSsOAwIaBQCgggFTMBgGCSqGSIb3DQEJ AzELBgkqhkiG9w0BBwEwHAYJKoZIhvcNAQkFMQ8XDTA1MDYxNTEyMTkyMlowIwYJKoZIhvcNAQkE MRYEFAKgwkCW1up4y16I3Ne55Lsq/3VqMHgGCSsGAQQBgjcQBDFrMGkwYjELMAkGA1UEBhMCWkEx JTAjBgNVBAoTHFRoYXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAqBgNVBAMTI1RoYXd0ZSBQ ZXJzb25hbCBGcmVlbWFpbCBJc3N1aW5nIENBAgMOeMcwegYLKoZIhvcNAQkQAgsxa6BpMGIxCzAJ BgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQD EyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgSXNzdWluZyBDQQIDDnjHMA0GCSqGSIb3DQEBAQUA BIIBAEZr21taGXdpgU2d++77gj/fUUIKLgdjNoIrGhmn524wleGTEkTD410/wdW+sDvUY+GCmRjQ LMjySFTujYuVcc+MGM4ZhQcIKnsG58yEmjOm4+m4LRd6Xtgxa+IAqtTrIiDbfTOKG54IN+YlENYY HS6K/IUDl1Kv77P93q5d8GGnGhmBRMP72EIv7cmoU2wR6rtDUhe2/ChIeOk8tjtUEYQsAlz98d75 Vpm36oDsSfy8gbqxRrii5tBa++9Sj2GA3Cq+2IU53RSqY37V1kPFpKDEq9j8bfl97BzYNBcM7Fnr JTFfoTBUw+lqjZmCMhllzOnmJXn3+PyFjDQs4lMsnoYAAAAAAAA= --Apple-Mail-3-944324957--