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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by sympa.inria.fr (Postfix) with ESMTPS id 208157F249 for ; Fri, 2 Nov 2012 17:00:57 +0100 (CET) Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.223.182; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail1-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.223.182 as permitted sender) identity=mailfrom; client-ip=209.85.223.182; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ie0-f182.google.com) identity=helo; client-ip=209.85.223.182; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-ie0-f182.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsUBAKLtk1DRVd+2m2dsb2JhbABEsR6SDwgjAQEBAQEICQsJFCeCHgEBBUABGxILAQMMBgULDQ0hIQEBEQEFAQoSBhMSh2UBAw8LnUGMMoJ3hHMKGScDClmIdQEFDIsOZ4Y7A5JHgV2BVYEciheDMBYphBI X-IronPort-AV: E=Sophos;i="4.80,699,1344204000"; d="scan'208";a="179926466" Received: from mail-ie0-f182.google.com ([209.85.223.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Nov 2012 17:00:56 +0100 Received: by mail-ie0-f182.google.com with SMTP id k10so9310051iea.27 for ; Fri, 02 Nov 2012 09:00:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=BFBsCY/XnjS4qalFjYbZCj3nuzZp93WO3+uNGBxN8hQ=; b=N+7s0Hbsy1/lYm1q/VVi51OKLmPcH3df5uLg98oYh8Dm+XQ4eAnbjRKOYYo6NqioNd ditQ0dplmsng/C8sdK7TWo+p6ymO3HisPNhPherH4N/1EC5iSwOIwHf2D91s3RQLd2/0 057oYOY4foiuqpCmk75YAiiZPD09KtAfJquaeQRZ0zOVJeCO/YDCHIXdXFDgIW3xu1eL chIl9lC16KKTTZokjcp2rDC6N29HYkzJ+N8JTg6uiPagH5oKNZlEeOcZyQKRL20ZDXK2 PuUpEmi55Qi8qBY3UHMcyElzMMITHkCH5qZzdHmghFPcUi/LLiUPSkmAgzJRvPL43KhW OgzQ== Received: by 10.50.140.97 with SMTP id rf1mr2220093igb.70.1351872055123; Fri, 02 Nov 2012 09:00:55 -0700 (PDT) MIME-Version: 1.0 Received: by 10.50.65.9 with HTTP; Fri, 2 Nov 2012 09:00:13 -0700 (PDT) In-Reply-To: <9d4b2966-a246-405e-a3fe-88e1667e5b96@googlegroups.com> References: <15ab226e-6bc3-4122-bb40-de8ae2a2339b@googlegroups.com> <9d4b2966-a246-405e-a3fe-88e1667e5b96@googlegroups.com> From: Gabriel Scherer Date: Fri, 2 Nov 2012 17:00:13 +0100 Message-ID: To: Radu Grigore Cc: Caml List 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 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, so I don't think you can do without the O(n log n) worst case bound. You could provide a specialized function that assumes that the mapping is order-preserving (you could even check it at runtime with no additional complexity cost, for added safety), but I'm not sure order-preserving mappings happen that often in practice. On Fri, Nov 2, 2012 at 4:11 PM, Radu Grigore wrote: > On Friday, November 2, 2012 2:59:17 PM UTC, Radu Grigore wrote: >> Somebody should put the linear time [of_list] in the standard library. > > Actually, that should probably be called [of_sorted_list], to make it clear what it does. If you worry about having a function that requires a sorted list, then note that there is already one in the standard library: List.merge. > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs