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 E51F37EE73 for ; Mon, 5 Nov 2012 13:02:04 +0100 (CET) Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of radugrigore@gmail.com) identity=pra; client-ip=209.85.212.54; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="radugrigore@gmail.com"; x-sender="radugrigore@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail1-smtp-roc.national.inria.fr: domain of radugrigore@gmail.com designates 209.85.212.54 as permitted sender) identity=mailfrom; client-ip=209.85.212.54; receiver=mail1-smtp-roc.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 (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-vb0-f54.google.com) identity=helo; client-ip=209.85.212.54; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="radugrigore@gmail.com"; x-sender="postmaster@mail-vb0-f54.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgYBABiql1DRVdQ2imdsb2JhbABEhhe9IwgjAQEBCgkNBxIGI4IeAQEEASMEGQEbCRQBAwELBgULDQICJgICIQEBEQEFARwGEwiHbwEDCQacBotiT4J3hDQKGScNWYh1AQUMgRSJeWiFKYETA5QmgVWBHIoXA4MtFimEEQ X-IronPort-AV: E=Sophos;i="4.80,714,1344204000"; d="scan'208";a="180174899" Received: from mail-vb0-f54.google.com ([209.85.212.54]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 05 Nov 2012 13:02:04 +0100 Received: by mail-vb0-f54.google.com with SMTP id l1so10400629vba.27 for ; Mon, 05 Nov 2012 04:02:03 -0800 (PST) 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=MOcxEAcCdbVh2tiCNiuoMoJBN7FTIpA1o6Yx8tUmQzQ=; b=i561lb9Nj6mTAKzGvHoLdv83Be/dS9GkdP6HcSbkHU+w4nzQST6y4m5ai9jmZA0l9l W6stf6X+RCYNt+NxCmlaWcCRMM6n3emJLpXrpGsOeDGGaILsh1za+AINPmXLaKOYRHW9 IKfLY5MQqgHBqAqA87OFoP8EQxt30N2WSfZUEfa2+uBp08p1pEbdxXJUM7vMq3ZhAf49 qwdB+voiaMxF1+FyNveDl8SjrvjIcMunWi7Bq91B1ycnAkR/7TggZ4fKic0a7Bo76zec /AYOFmI5a98sClCxfDKKMiS+ClmaTeCdEXKQXa79tM/j81nB6NA6EdEsSMH7mZIe2Z0c x5Xw== MIME-Version: 1.0 Received: by 10.220.150.14 with SMTP id w14mr9197773vcv.13.1352116923428; Mon, 05 Nov 2012 04:02:03 -0800 (PST) Received: by 10.58.69.81 with HTTP; Mon, 5 Nov 2012 04:02:03 -0800 (PST) In-Reply-To: References: <9da48315-639b-4de2-a3d5-f86685602425@googlegroups.com> Date: Mon, 5 Nov 2012 12:02:03 +0000 Message-ID: From: Radu Grigore To: Gabriel Scherer Cc: fa.caml@googlegroups.com, 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 Mon, Nov 5, 2012 at 10:12 AM, Gabriel Scherer wrote: > You haven't tested the bad case, where the list is nearly sorted but > not exactly It's 3.7% slower, rather than 3.6% for random lists. (But, you shouldn't be calling it "*the* bad case".) > Another problem is that you call the > user-defined comparison more than necessary, [...] I would note only that the "necessary" number of comparisons is not really achieved with your optimization, for the simple reason that the minimum number of comparisons is hard to compute. [1] > pay costs that a demanding user could request to skip by having > of_sorted_list and of_list exposed directly, and making the choice > herself. I'm not sure what costs you are talking about: (1) If it's the case of sorted lists, then that user is already paying a much bigger price now. (2) It it's the case of non-sorted lists, then the demanding user can always do what they do now. > A note on API design: [...] My personal opinion is that we > should preserve the abstraction of Set and Map, reject all operations > that rely on a representation assumption of sorted balanced trees > (unfortunately some of them, such as split, have already crept in), The (of_list : elt list -> t) function relies on no assumption about how the set is implemented. With *any* reasonable implementation of a set, you should be able to build it from a list. The only reason to *not* put it in the interface would be if the user could write an implementation that is just as good. But they can't. [1] http://oeis.org/A036604