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

[Radu Grigore <radugrigore@gmail.com>]

Nice.  I'll show you an alternative.

In your solution you write
  let chrs = CharSet.map (module StringSet) strs (fun s -> s.[0])
In my solution you write
  let chrs = CharSet.of_list (StringSet.map_l strs (fun s -> s.[0]))
It has about the same length.

The disadvantage of my solution is that the type of map_l is weird
  StringSet.map_l : StringSet.t -> (string -> 'a) -> 'a list

The advantages are
1. It is possible to implement in O(n), rather than O(n lg n)
2. Works in 3.12.
Somebody should put the linear time [of_list] in the standard library.

Here is a simple, O(n lg n) implementation, similar to yours.

  module FunkySet = struct
    module type OrderedType = Set.OrderedType
    module type S = Set.S
    module Make (E : OrderedType) = struct
      include Set.Make (E)
      let of_list xs = List.fold_right add xs empty
      let map_l s f = List.map f (elements s)
    end
  end