From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA09039; Mon, 26 Jul 2004 17:47:26 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA08445 for ; Mon, 26 Jul 2004 17:47:25 +0200 (MET DST) Received: from out2.smtp.messagingengine.com (out2.smtp.messagingengine.com [66.111.4.26]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6QFlOEV014607 for ; Mon, 26 Jul 2004 17:47:25 +0200 X-Sasl-enc: UsJ7qJssCF7hacUzGdoyTg 1090856841 Received: from [192.168.1.100] (unknown [218.81.125.200]) by mail.messagingengine.com (Postfix) with ESMTP id 4F47EC12EA0; Mon, 26 Jul 2004 11:47:19 -0400 (EDT) Date: Mon, 26 Jul 2004 23:47:09 +0800 (HKT) From: Martin Jambon X-X-Sender: martin@localhost To: Brian Hurt Cc: Matthieu Sozeau , Subject: Re: [Caml-list] Map + Set In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at nez-perce with ID 4105278C.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 matthieu:01 2004:99 val:01 elt:01 elt:01 pervasives:01 descend:01 matthieu:01 predicate:01 unsafe:01 equality:01 equality:01 int:01 int:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, 26 Jul 2004, Brian Hurt wrote: > On Mon, 26 Jul 2004, Matthieu Sozeau wrote: > > > On Sun, Jul 25, 2004 at 12:01:03PM -0500, Brian Hurt wrote: > > > On Sun, 25 Jul 2004, Martin Jambon wrote: > > > > > > A better interface might be: > > > > > > val find: (elt -> int) -> t -> elt ^^^^^^^^^^^^ This is a little unsafe, isn't it? What if you don't respect the ordering of your set? > > Why an int ? Isn't a boolean enough ? > > Two reasons: > > 1) This allows you to use Pervasives.compare (or other compatible > function) partially applied. > > 2) In addition to equality, you also need less than/greater than in order > to keep the function in O(log N)- which branch do you descend? With just > equality, you need to do an O(N) exhaustive search. I think Brian and Matthieu are talking about 2 different things: (1) Martin and Brian were talking of an O(log n) find just like mem. (2) Matthieu and others are talking of a search using an arbitrary predicate just like List.find, in O(n) steps. Martin ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners