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 mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by sympa.inria.fr (Postfix) with ESMTPS id 753AE7F249 for ; Fri, 2 Nov 2012 17:21:29 +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.220.182; 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.220.182 as permitted sender) identity=mailfrom; client-ip=209.85.220.182; 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-vc0-f182.google.com) identity=helo; client-ip=209.85.220.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="radugrigore@gmail.com"; x-sender="postmaster@mail-vc0-f182.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: At8CAKjyk1DRVdy2lGdsb2JhbABEhhe9FggjAQEBAQkJCwkSKYIeAQEEASMdARsdAQMBCwYFCw0CAiYCAiEBAREBBQEcBhOHdwEDCQadUYtjT4J3hHUKGScNWYh1AQUMgRSJemeFKIETA5JHgV2BVYszgzAWKYQR X-IronPort-AV: E=Sophos;i="4.80,701,1344204000"; d="scan'208";a="161202171" Received: from mail-vc0-f182.google.com ([209.85.220.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Nov 2012 17:21:28 +0100 Received: by mail-vc0-f182.google.com with SMTP id fw7so7141804vcb.27 for ; Fri, 02 Nov 2012 09:21:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=P9XGe6QXAEcse+a3XW+nFj7DFVKd8Th+/oLGNACr1ZM=; b=nfajGZdO/0BogkKRJ4K47qAJZFGA3HiD4IsJ3ZkToWBHNIDDt0/nYIqRt2b4L3ehaX ewtrWO9RGvv5GgDP0qsj/QPE4x14uPrARrrS4OnGoKcKn/i++yRKxZEh6XAOIiQxZfgP qg/E6Xqezlnd++hDtWiAoKEdN0Cc5SkAmreu3yQOeMkoxAdyF1H/nFHsRuHdhb8Bjx12 1/EHonS54lQrnldsytgLOItQH/5Ud0Y6QzP+MrCrGbdRWdyHgZ5kzn4wd6hdeyRxpJ/R vhvfDMQjo1w2iADTemtnsoO+msWt0slgEO7DCpzOZ+lUSw/p7hmqLLO7/ElMLnDZComx nRDQ== MIME-Version: 1.0 Received: by 10.52.29.148 with SMTP id k20mr2039725vdh.37.1351873287166; Fri, 02 Nov 2012 09:21:27 -0700 (PDT) Received: by 10.58.69.81 with HTTP; Fri, 2 Nov 2012 09:21:27 -0700 (PDT) In-Reply-To: References: <15ab226e-6bc3-4122-bb40-de8ae2a2339b@googlegroups.com> <9d4b2966-a246-405e-a3fe-88e1667e5b96@googlegroups.com> Date: Fri, 2 Nov 2012 16:21:27 +0000 Message-ID: From: Radu Grigore To: Gabriel Scherer Cc: Caml List Content-Type: text/plain; charset=UTF-8 Subject: Re: [Caml-list] Writing the function Set.map using first-class modules and 4.00 inference On Fri, Nov 2, 2012 at 4:00 PM, Gabriel Scherer wrote: > But when you map from an ASet to a BSet, there is no reason to assume > in general that the mapping function preserves the order, Oops. > I don't think you can do without the O(n log n) worst case bound. Probably not. > I'm not sure order-preserving mappings happen that often in practice. I can't remember a single instance where I needed to map between sets, order-preserving or not. I do, however, often make sets out of lists. In a few cases I know that the list is sorted by construction. I would like to have [of_sorted_list]. Or (better?) an [of_list] that works in O(n) for sorted lists and falls back to O(n lg n) when the list isn't already sorted. This can't be done without messing with Set's internals, which is why I think it should be in the interface.