From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 95F2F7F706 for ; Fri, 17 Jan 2014 15:31:36 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.214.44; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.214.44 as permitted sender) identity=mailfrom; client-ip=209.85.214.44; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-bk0-f44.google.com) identity=helo; client-ip=209.85.214.44; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-bk0-f44.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqABAJFf2FLRVdYsm2dsb2JhbABZg0NWqCiSaYEHCBYOAQEBAQEGCwsJFCiCJQEBAQQnGQETCBILAQMMBgULDQ0hIgERAQUBChIGExKHXQEDEQ2dDoxcgwmSFAoZJwMKZIRyEQEFDI5zB4Q4BJQ7g2aBMYkshU0YKYRaOw X-IPAS-Result: AqABAJFf2FLRVdYsm2dsb2JhbABZg0NWqCiSaYEHCBYOAQEBAQEGCwsJFCiCJQEBAQQnGQETCBILAQMMBgULDQ0hIgERAQUBChIGExKHXQEDEQ2dDoxcgwmSFAoZJwMKZIRyEQEFDI5zB4Q4BJQ7g2aBMYkshU0YKYRaOw X-IronPort-AV: E=Sophos;i="4.95,670,1384297200"; d="scan'208";a="53724670" Received: from mail-bk0-f44.google.com ([209.85.214.44]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 17 Jan 2014 15:31:36 +0100 Received: by mail-bk0-f44.google.com with SMTP id ej10so1672000bkb.3 for ; Fri, 17 Jan 2014 06:31:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=Rym0H7SsJ0mub0J+rPcbwSJJpe2z6O2WK9W5qX9ayug=; b=Ep4PzHZSmC2+TOuMXfXDwxWOouaxEUbMe+owe/V0EhHg2nGx+i48hm7CibEra8VFuM XdsVEhcqJm7ZaBy1PWOpDLYB6hsxXKLxRZsxsIItjJRkVDq1RkCYM7eWsqKkr7I1LqKj 5sPXaEv4HOVR5krM/I9LQ+y+XwlrXhbA76CofEGPyT/hKGN2mueUnUyPOmbTkcZc9JL9 cOdhJMPNHlfbyAEF3ORzSHqj8nN4y5xvLtYziQi+Jbmu8uABR8LwwrhPFlQM9aV7GHpa i3hGJYGdf/e34CmhAJJFMUmqNuU3oGRfrSiQk04MADPJPd2/8B6Eq2JDs8FRjd6700Uz V8Cw== X-Received: by 10.204.73.2 with SMTP id o2mr521581bkj.55.1389969095807; Fri, 17 Jan 2014 06:31:35 -0800 (PST) MIME-Version: 1.0 Received: by 10.205.45.5 with HTTP; Fri, 17 Jan 2014 06:30:55 -0800 (PST) In-Reply-To: <20140117151030.Horde.4IXAJuUEQPnzcftAlxa4vw4@wmail.univ-bpclermont.fr> References: <20140117151030.Horde.4IXAJuUEQPnzcftAlxa4vw4@wmail.univ-bpclermont.fr> From: Gabriel Scherer Date: Fri, 17 Jan 2014 15:30:55 +0100 Message-ID: To: SEROT Jocelyn Cc: caml users Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [Caml-list] Need help with higher order functors In your implementation, you can change module R = Set.Make(P) into module R = Set.Make(C(E1)(E2)) Or simply use: struct module S1 = Set.Make (E1) module S2 = Set.Make (E2) include Set.Make(C(E1)(E2)) type t1 = S1.t type t2 = S2.t module P = C(E1)(E2) let product s1 s2 = let f x y t = add (P.product x y) t in let g x t = S2.fold (f x) s2 t in S1.fold g s1 empty end On Fri, Jan 17, 2014 at 3:10 PM, SEROT Jocelyn wrote: > Hi, > > I'm trying to implement an extension of the Set module including the notion > of cartesian product. > > The interface of the module is : > > (** File pset.mli *) > > module type ELT_PROD = sig > include Set.OrderedType > type t1 > type t2 > val product: t1 -> t2 -> t > end > > module type SET_PROD = sig > include Set.S > type t1 > type t2 > val product: t1 -> t2 -> t > end > > module MakeProduct > (E1: Set.OrderedType) > (E2: Set.OrderedType) > (C: functor (E1: Set.OrderedType) -> functor (E2: Set.OrderedType) -> > ELT_PROD with type t1 = E1.t and type t2 = E2.t) > : SET_PROD > with type t1 = Set.Make(E1).t > and type t2 = Set.Make(E2).t > and type t = Set.Make(C(E1)(E2)).t > and type elt = C(E1)(E2).t > > The [MakeProduct] functor takes the signature of element types and a functor > describing how to combine these elements for building the set product. > An "obvious" definition of such a functor could be > > module MakePair (E1: Set.OrderedType) (E2: Set.OrderedType) = struct > type t = E1.t * E2.t > let compare = Pervasives.compare > type t1 = E1.t > type t2 = E2.t > let product x y = x,y > end > > so that the definition of the "natural" cartesian product of two sets with > with elements having sig Int and Bool resp., should be > > module IntBoolSet = MakeProduct (Int) (Bool) (MakePair) > > but taking an extra functor argument for [MakeProduct] allows specialized > definitions of the product. For example, here's an alternative definition of > the MakePair functor which > could be passed to MakeProduct : > > module MakePair' (E1: Set.OrderedType) (E2: Set.OrderedType) = struct > type t = Pair of E1.t * E2.t > let compare = Pervasives.compare > type t1 = E1.t > type t2 = E2.t > let product x y = Pair (x,y) > end > > The problem i have is in the implementation of the Mset module : > > (** File mset.ml *) > > module type SET_PROD = sig > include Set.S > type t1 > type t2 > val product: t1 -> t2 -> t > end > > module type ELT_PROD = sig > include Set.OrderedType > type t1 > type t2 > val product: t1 -> t2 -> t > end > > module MakeProduct > (E1: Set.OrderedType) > (E2: Set.OrderedType) > (C: functor (E1: Set.OrderedType) -> functor (E2: Set.OrderedType) -> > ELT_PROD with type t1 = E1.t and type t2 = E2.t) = > struct > module S1 = Set.Make (E1) > module S2 = Set.Make (E2) > module P = C (E1) (E2) > module R = Set.Make(P) > include R > type t1 = S1.t > type t2 = S2.t > let product s1 s2 = > let f x y t = R.add (P.product x y) t in > let g x t = S2.fold (f x) s2 t in > S1.fold g s1 R.empty > end > > Unfortunately, this does not compile. I get a long error message, ending > with : > > (* excerpt of the compiler log : *) > > module R : > sig > type elt = P.t > type t = Set.Make(P).t > val empty : t > ... > end > type elt = P.t > type t = Set.Make(P).t > val empty : t > .... > type t1 = S1.t > type t2 = S2.t > val product : S1.t -> S2.t -> R.t > end > is not included in > sig > type elt = C(E1)(E2).t > type t = Set.Make(C(E1)(E2)).t > val empty : t > ... > type t1 = Set.Make(E1).t > type t2 = Set.Make(E2).t > val product : t1 -> t2 -> t > end > Type declarations do not match: > type t = Set.Make(P).t > is not included in > type t = Set.Make(C(E1)(E2)).t > > I suspect that some sharing constraint is missing here, but cannot spot > where. > I was expecting that declaration > module P = C (E1) (E2) > in the functor definition should automatically enforce the equality of types > P.t and C(E1)(E2).t, and, hence, of types Set.Make(P).t and > Set.Make(C(E1)(E2)).t. > Obviously not. > > Any help would be greatly appreciated ;) > > Thanks in advance, > > Jocelyn > > > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs