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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 12D867F02D for ; Tue, 21 Oct 2014 14:26:19 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of lpw25@cam.ac.uk) identity=pra; client-ip=131.111.8.140; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="lpw25@cam.ac.uk"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of lpw25@cam.ac.uk) identity=mailfrom; client-ip=131.111.8.140; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="lpw25@cam.ac.uk"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@ppsw-40.csi.cam.ac.uk) identity=helo; client-ip=131.111.8.140; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="postmaster@ppsw-40.csi.cam.ac.uk"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AiMEAMRIRlSDbwiMnGdsb2JhbABcg2FYgwa2CgaSf4dVAoEOFgERAQEBAQEICwkJFC6EAwEBAwEjBFIFCwsaAgUhAgIPAQRJLogcCASuLY8UhVcBAQgBAQEBHhiBFIR3iXszB4J3gVQFlkeIQzyQNYd5a4JLAQEB X-IPAS-Result: AiMEAMRIRlSDbwiMnGdsb2JhbABcg2FYgwa2CgaSf4dVAoEOFgERAQEBAQEICwkJFC6EAwEBAwEjBFIFCwsaAgUhAgIPAQRJLogcCASuLY8UhVcBAQgBAQEBHhiBFIR3iXszB4J3gVQFlkeIQzyQNYd5a4JLAQEB X-IronPort-AV: E=Sophos;i="5.04,762,1406584800"; d="scan'208";a="84084242" Received: from ppsw-40.csi.cam.ac.uk ([131.111.8.140]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 21 Oct 2014 14:26:18 +0200 X-Cam-AntiVirus: no malware found X-Cam-ScannerInfo: http://www.cam.ac.uk/cs/email/scanner/ Received: from host86-181-34-203.range86-181.btcentralplus.com ([86.181.34.203]:44191 helo=netbook) by ppsw-40.csi.cam.ac.uk (smtp.hermes.cam.ac.uk [131.111.8.156]:587) with esmtpsa (PLAIN:lpw25) (TLSv1.2:AES128-GCM-SHA256:128) id 1XgYW1-0005qX-js (Exim 4.82_3-c0e5623) (return-path ); Tue, 21 Oct 2014 13:26:17 +0100 From: Leo White To: Arnaud Spiwack Cc: OCaML Mailing List References: X-Face: "XWxb[u_Z\PA_Y?9@|IA!!+jTb(/290-*ea/Un$I0B98.$n%eL.;2w*,z]WR#T:,p[ NBd++M7l]#7zj7!{~iw $W-"/=|dVjhT[D{4~gE}gK<2`.6fs!;uqqud]vs2N/3^m7{aS1V, Date: Tue, 21 Oct 2014 13:26:13 +0100 In-Reply-To: (Arnaud Spiwack's message of "Tue, 21 Oct 2014 10:52:02 +0200") Message-ID: <8638ahpq1m.fsf@cam.ac.uk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] Manipulating Modules Modularly > module type M =3D sig=C2=A0 type t=C2=A0 val u:t=C2=A0 val p:t->t->t=C2= =A0 end > > And a functor: > > module type ME =3D sig=C2=A0 type t=C2=A0 val ps:t list -> t=C2=A0 end > module ME (M:M) : ME with type t :=3D M.t > > All good and well. I now want to reuse my functor for list, which are a m= onoid. > What I really want is a module > > module LE : ME with type t :=3D 'a list > > So here's my question: how do you/would you solve this problem. If the so= lution is compatible with 3.12, it's a plus. > Moving quantifiers around is awkward in the module system, but is also not safe in general. We can clearly illustrate this by reencoding your example without modules: First we define `m` as a record type and create one for lists: # type 'a m =3D { u : 'a; p : 'a -> 'a -> 'a };; type 'a m =3D { u : 'a; p : 'a -> 'a -> 'a; } # let list =3D { u =3D []; p =3D (@) };; val list : 'a list m =3D {u =3D []; p =3D } Then we define the `me` as another record type and create a simple function for creating them from monoids: # type 'a me =3D { ps : 'a list -> 'a };; type 'a me =3D { ps : 'a list -> 'a; } # let me (m : 'a m) =3D { ps =3D List.fold_left m.p m.u };; val me : 'a m -> 'a me =3D Now we can apply the `me` function to the `list` monoid: # let mel =3D me list;; val mel : '_a list me =3D {ps =3D } But what we get is only weakly polymophic because of the value restriction. This hints at the unsafety of what we are trying to do. Whilst the above definition of `me` happens to be safe, consider the following version: # let me (m : 'a m) =3D let r =3D ref m.u in let ps =3D function | [] -> !r | x :: xs -> let old =3D !r in r :=3D x; List.fold_left m.p m.u (old :: xs) in {ps};; val me : 'a m -> 'a me =3D # let mel =3D me list;; val mel : '_a list me =3D {ps =3D } Here we use a reference to preserve elements of the monoid across different calls to `ps`. If this were allowed to be polymorphic we could end up mixing elements of different list types together. For example, if we use `Obj.magic` to pretend that `mel` is polymorphic we can quickly get a segfault: # let meli : int list me =3D Obj.magic mel;; val meli : int list me =3D {ps =3D } # let melf : float list me =3D Obj.magic mel;; val melf : float list me =3D {ps =3D } # meli.ps [[1; 2; 3]; [2; 3; 4]];; - : int list =3D [2; 3; 4] # melf.ps [[1.0; 2.0; 3.0]; [2.0; 3.0; 4.0]];; Process ocaml-toplevel segmentation fault So hopefully, this illustrates why you cannot easily get what you want in a language with side-effects. Since what you are fundementally trying to do is safe, I suspect that a language with good support for higher-rank polymorphism, higher-kinded polymorphism, and kind polymorphism might be apply to encode it safely even in the presence of side-effects, but the encoding is likely to be a bit involved. Regards, Leo