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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by sympa.inria.fr (Postfix) with ESMTPS id DB7A37F249 for ; Thu, 1 Nov 2012 22:00:02 +0100 (CET) Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of nanaki@gmail.com) identity=pra; client-ip=209.85.160.54; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="nanaki@gmail.com"; x-sender="nanaki@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail1-smtp-roc.national.inria.fr: domain of nanaki@gmail.com designates 209.85.160.54 as permitted sender) identity=mailfrom; client-ip=209.85.160.54; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="nanaki@gmail.com"; x-sender="nanaki@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-pb0-f54.google.com) identity=helo; client-ip=209.85.160.54; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="nanaki@gmail.com"; x-sender="postmaster@mail-pb0-f54.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtwCAEviklDRVaA2k2dsb2JhbABEwy8IIwEBAQEJCRQUBCOCTBkBGx4DEgkHXQERAQUBIogGAQMPm0CCcowygnaFFAoZJw1ZiHUBBQySKgOIWo0ejmIWKYQx X-IronPort-AV: E=Sophos;i="4.80,695,1344204000"; d="scan'208";a="179847843" Received: from mail-pb0-f54.google.com ([209.85.160.54]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 01 Nov 2012 22:00:01 +0100 Received: by mail-pb0-f54.google.com with SMTP id rp8so2592431pbb.27 for ; Thu, 01 Nov 2012 14:00:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=4aGRoSZ+3NYdQjF9qk3uhxIAfAqZGkBBf7jG/kxpa+M=; b=nlVP2s7r/iBVOOxH7wc2lk+5koITqnltj3cGYvCnW06hpTy9bVVcXYTcJk/hVzEn7b DjWZEGCPvspFk6d0yrwCoHneTxZAeniuzQ8hvTblql+yQGyTAlqOtLnPGmKG+5PjAPSj /371EQkQggITkUMdpeh1sSD9R44Wa1jPBZAFrHvefrGR8j3x4znBqJmgxncCNqKswXs6 iEx8rJA4aeGs3XMQxbrcAYcAspIscnvyHzLX7I1ZXzZMArJDg78VY6ffrx56XCGbTHe8 RwF2kHi+BpWzH6XHKAJKFU1tGDuTTZ0KxgBNGLBJncKq/nNJN+BGUuLTrqU2OCGW8pi2 4MVw== MIME-Version: 1.0 Received: by 10.69.0.10 with SMTP id au10mr126876906pbd.18.1351803600180; Thu, 01 Nov 2012 14:00:00 -0700 (PDT) Received: by 10.66.221.104 with HTTP; Thu, 1 Nov 2012 14:00:00 -0700 (PDT) Date: Thu, 1 Nov 2012 14:00:00 -0700 Message-ID: From: Jeff Meister To: Caml List Content-Type: multipart/alternative; boundary=047d7b16050565151004cd754d61 Subject: [Caml-list] Writing the function Set.map using first-class modules and 4.00 inference --047d7b16050565151004cd754d61 Content-Type: text/plain; charset=ISO-8859-1 I found an interesting (to me, anyway) use of OCaml's first-class modules, and particularly the new 4.00 type inference features, which I thought was worth sharing with the list. This has probably been observed by someone else already, but I haven't seen it discussed. In the OCaml standard library, the polymorphic set data structure is implemented as a functor, which takes a module containing a type t and total ordering function over t, and returns a module representing sets whose elements have type t. Like so: module StringSet = Set.Make(String) module CharSet = Set.Make(Char) One disadvantage of this method is that once the functor has been called, the type of the set elements is fixed. As a consequence, OCaml's set interface has no map function. If we had a polymorphic type like 'a set, this function would have type 'a set -> ('a -> 'b) -> 'b set. But StringSet.t and CharSet.t are not polymorphic; the corresponding type elt in each module cannot be changed. However, using first-class modules, we can write a function map for sets, which takes as an extra argument the packaged module representing the set we're mapping from. Maybe this function is better called map_from. Check it out: # module Set = struct module type OrderedType = Set.OrderedType module type S = Set.S module Make(Ord : OrderedType) = struct include Set.Make(Ord) let map (type e') (type t') (module OtherSet : S with type elt = e' and type t = t') os f = OtherSet.fold (fun x accu -> add (f x) accu) os empty end end;; [... bunch of output ...] val map : (module S with type elt = 'a and type t = 'b) -> 'b -> ('a -> elt) -> t Now, back in OCaml 3.12, this function could be written (without the nice package-expanding pattern I've made use of), but calling it was quite a pain, enough to invalidate the whole enterprise. One would have to type this: # let strs = StringSet.(add "foo" (add "bar" empty));; val strs : StringSet.t = # let chrs = CharSet.map (module StringSet : Set.S with type elt = StringSet.elt and type t = StringSet.t) strs (fun s -> s.[0]);; val chrs : CharSet.t = It's much easier with the type inference changes in OCaml 4.00: # let strs = StringSet.(add "foo" (add "bar" empty));; val strs : StringSet.t = # let chrs = CharSet.map (module StringSet) strs (fun s -> s.[0]);; val chrs : CharSet.t = --047d7b16050565151004cd754d61 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable I found an interesting (to me, anyway) use of OCaml's first-class modul= es, and particularly the new 4.00 type inference features, which I thought = was worth sharing with the list. This has probably been observed by someone= else already, but I haven't seen it discussed.

In the OCaml standard library, the polymorphic set data structure is im= plemented as a functor, which takes a module containing a type t and total = ordering function over t, and returns a module representing sets whose elem= ents have type t. Like so:

module StringSet =3D Set.Make(String)
module CharSet =3D Set.Make(Ch= ar)

One disadvantage of this method is that once the functor has bee= n called, the type of the set elements is fixed. As a consequence, OCaml= 9;s set interface has no map function. If we had a polymorphic type like &#= 39;a set, this function would have type 'a set -> ('a -> '= ;b) -> 'b set. But StringSet.t and CharSet.t are not polymorphic; th= e corresponding type elt in each module cannot be changed.

However, using first-class modules, we can write a function map for set= s, which takes as an extra argument the packaged module representing the se= t we're mapping from. Maybe this function is better called map_from. Ch= eck it out:

# module Set =3D struct
=A0=A0=A0 module type OrderedType =3D Set.Or= deredType
=A0=A0=A0 module type S =3D Set.S
=A0=A0=A0 module Make(Ord= : OrderedType) =3D struct
=A0=A0=A0=A0=A0 include Set.Make(Ord)
=A0= =A0=A0=A0=A0 let map (type e') (type t') (module OtherSet : S with = type elt =3D e' and type t =3D t') os f =3D
=A0=A0=A0=A0=A0=A0 OtherSet.fold (fun x accu -> add (f x) accu) os empty=
=A0=A0 end
=A0end;;
[... bunch of output ...]
val map :
=A0= (module S with type elt =3D 'a and type t =3D 'b) ->
=A0 = 9;b -> ('a -> elt) -> t

Now, back in OCaml 3.12, this function could be written (without the ni= ce package-expanding pattern I've made use of), but calling it was quit= e a pain, enough to invalidate the whole enterprise. One would have to type= this:

# let strs =3D StringSet.(add "foo" (add "bar" empt= y));;
val strs : StringSet.t =3D <abstr>
# let chrs =3D CharSet= .map (module StringSet : Set.S with type elt =3D StringSet.elt and type t = =3D StringSet.t) strs (fun s -> s.[0]);;
val chrs : CharSet.t =3D <abstr>

It's much easier with the= type inference changes in OCaml 4.00:

# let strs =3D StringSet.(add= "foo" (add "bar" empty));;
val strs : StringSet.t = =3D <abstr>
# let chrs =3D CharSet.map (module StringSet) strs (fun s -> s.[0]);;val chrs : CharSet.t =3D <abstr>
--047d7b16050565151004cd754d61--