[Caml-list] Writing the function Set.map using first-class modules and 4.00 inference

[Jeff Meister <nanaki@gmail.com>]

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

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 = <abstr>
# 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 = <abstr>

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 = <abstr>
# let chrs = CharSet.map (module StringSet) strs (fun s -> s.[0]);;
val chrs : CharSet.t = <abstr>

[-- Attachment #2: Type: text/html, Size: 2693 bytes --]