Re: [Caml-list] Map + Set

[Martin Jambon <martin_jambon@emailuser.net>]

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