Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Map + Set
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Martin Jambon <martin_jambon@e...>
Subject: Re: [Caml-list] Map + Set
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