From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <radugrigore@gmail.com>
X-Original-To: caml-list@sympa.inria.fr
Delivered-To: caml-list@sympa.inria.fr
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by sympa.inria.fr (Postfix) with ESMTPS id 8B0AD7F249
	for <caml-list@sympa.inria.fr>; Fri,  2 Nov 2012 15:59:20 +0100 (CET)
Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender
  authenticity information available from domain of
  radugrigore@gmail.com) identity=pra;
  client-ip=209.85.210.190;
  receiver=mail4-smtp-sop.national.inria.fr;
  envelope-from="radugrigore@gmail.com";
  x-sender="radugrigore@gmail.com";
  x-conformance=sidf_compatible
Received-SPF: Pass (mail4-smtp-sop.national.inria.fr: domain of
  radugrigore@gmail.com designates 209.85.210.190 as permitted
  sender) identity=mailfrom; client-ip=209.85.210.190;
  receiver=mail4-smtp-sop.national.inria.fr;
  envelope-from="radugrigore@gmail.com";
  x-sender="radugrigore@gmail.com";
  x-conformance=sidf_compatible; x-record-type="v=spf1"
Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@mail-ia0-f190.google.com) identity=helo;
  client-ip=209.85.210.190;
  receiver=mail4-smtp-sop.national.inria.fr;
  envelope-from="radugrigore@gmail.com";
  x-sender="postmaster@mail-ia0-f190.google.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AtcBAJDek1DRVdK+kWdsb2JhbABEwy0IIwEBAQEJCQ0HEimCHwEBBAEBASQ1HRALRiMRAQUBHDSHXAESnTWMModnChmBDYh7jxiDJAOIWpwCP4Qx
X-IronPort-AV: E=Sophos;i="4.80,699,1344204000"; 
   d="scan'208";a="161195733"
Received: from mail-ia0-f190.google.com ([209.85.210.190])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Nov 2012 15:59:19 +0100
Received: by mail-ia0-f190.google.com with SMTP id u21so2263999ial.27
        for <caml-list@inria.fr>; Fri, 02 Nov 2012 07:59:17 -0700 (PDT)
Received: by 10.52.97.101 with SMTP id dz5mr388107vdb.2.1351868357495; Fri, 02
 Nov 2012 07:59:17 -0700 (PDT)
Path: glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: fa.caml
Date: Fri, 2 Nov 2012 07:59:17 -0700 (PDT)
In-Reply-To: <fa.FUGAe9RTYsSPA4RwbpKO14B0oVo@ifi.uio.no>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=138.37.90.78; posting-account=e5mzsQoAAAB7g9y7Bkgam0zJDHRr7bCB
NNTP-Posting-Host: 138.37.90.78
References: <fa.FUGAe9RTYsSPA4RwbpKO14B0oVo@ifi.uio.no>
User-Agent: G2/1.0
X-Google-Web-Client: true
X-Google-IP: 138.37.90.78
MIME-Version: 1.0
Message-ID: <15ab226e-6bc3-4122-bb40-de8ae2a2339b@googlegroups.com>
From: Radu Grigore <radugrigore@gmail.com>
To: fa.caml@googlegroups.com
Cc: Caml List <caml-list@inria.fr>
Content-Type: text/plain; charset=ISO-8859-1
Subject: Re: [Caml-list] Writing the function Set.map using first-class
 modules and 4.00 inference

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