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

Article View: fa.caml

Article #90

#90

From: Radu Grigore
Date: Fri, 02 Nov 2012 14:59

27 lines
2218 bytes

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

Technical Details

Message-ID: <15ab226e-6bc3-4122-bb40-de8ae2a2339b@googlegroups.com>

Path:

arc1-ca.pugleaf.net!gf5ni14056677qab.0!nntp.google.com!c7no3365200qap.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail

References: <fa.FUGAe9RTYsSPA4RwbpKO14B0oVo@ifi.uio.no>

Show Full Headers

Complete Article Headers

X-Google-Thread: c0fe4b917e,1e67767467266ae5
X-Google-Attributes: gidc0fe4b917e,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII-7-bit
Received: by 10.224.207.66 with SMTP id fx2mr1039362qab.7.1351868357519;
        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: arc1-ca.pugleaf.net!gf5ni14056677qab.0!nntp.google.com!c7no3365200qap.0!postnews.google.com!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
MIME-Version: 1.0
Message-ID: <15ab226e-6bc3-4122-bb40-de8ae2a2339b@googlegroups.com>
Subject: Re: [Caml-list] Writing the function Set.map using first-class
 modules and 4.00 inference
From: Radu Grigore <radugrigore@gmail.com>
Cc: Caml List <caml-list@inria.fr>
Injection-Date: Fri, 02 Nov 2012 14:59:17 +0000
Content-Type: text/plain; charset=ISO-8859-1

Reply to Parent Message