Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

No find operation in Set #5864

Closed
vicuna opened this issue Dec 26, 2012 · 11 comments
Closed

No find operation in Set #5864

vicuna opened this issue Dec 26, 2012 · 11 comments

Comments

@vicuna
Copy link

vicuna commented Dec 26, 2012

Original bug ID: 5864
Reporter: berenger
Assigned to: @alainfrisch
Status: closed (set by @xavierleroy on 2015-12-11T18:18:22Z)
Resolution: fixed
Priority: normal
Severity: feature
Platform: All
OS: All
OS Version: All
Version: 4.00.0
Fixed in version: 4.01.0+dev
Category: standard library
Monitored by: @hcarty

Bug description

I find myself with the following use case:
I'd like to find back some element I have put in a Set.

There is choose:
val choose : t -> elt
"Return one element of the given set, or raise Not_found if the set is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal sets."

I'd like a find:
val find : elt -> t -> elt
the element to find is specified by an element that compares equal
to the one provided.

Currently, I switched to using a Map, but I am not sure this is
as efficient as a Set.

@vicuna
Copy link
Author

vicuna commented Dec 29, 2012

Comment author: meyer

Why not use Set.mem, am I missing something?

Set.find would return the same element or throw an exception, I don't think there is a justified usage pattern for this, but I am happy to see it otherwise if you show me an example how it would be useful.

@vicuna
Copy link
Author

vicuna commented Dec 29, 2012

Comment author: @hcarty

Set.find is useful when the comparison function does not provide a complete ordering of potential set elements. For a contrived example:

module Elt = struct
type t = { x : int; y : int }
let compare a b = compare a.x b.x
end

module S = Set.Make(Elt)

In this case, S.find can tell you what specific value (if any) is already in the set. S.mem could not.

@vicuna
Copy link
Author

vicuna commented Jan 4, 2013

Comment author: berenger

hcarty is right: my use case is exactly of this kind.

@vicuna
Copy link
Author

vicuna commented Jan 4, 2013

Comment author: berenger

This might be the code for set.ml.
I don't know which mli files are impacted by this new function
as I am not used to mli files.

let rec find x = function
Empty -> raise Not_found
| Node(l, v, r, _) ->
let c = Ord.compare x v in
if c = 0 then v
else find x (if c < 0 then l else r)

@vicuna
Copy link
Author

vicuna commented Jan 4, 2013

Comment author: thelema

If you're using a set for this kind of operation, you're doing it wrong; this use case is exactly what Map is for; why not use it?

@vicuna
Copy link
Author

vicuna commented Jan 5, 2013

Comment author: @alainfrisch

There could indeed be legitimate use of a Set.find function, e.g. when sets are used to implement some kind of hash-consing. Since the data structure easily supports it, I don't see why we should force the user to switch to identity maps.

@vicuna
Copy link
Author

vicuna commented Jan 8, 2013

Comment author: berenger

If I send a patch with the code, is there a chance it would be accepted?

@vicuna
Copy link
Author

vicuna commented Jan 8, 2013

Comment author: @alainfrisch

No need for a patch, I've committed your implementation (commit 13211 on trunk).

@vicuna
Copy link
Author

vicuna commented Jan 8, 2013

Comment author: berenger

Wow, nice.

Maybe the ocamldoc:

(** [find x s] returns the element of [s] equal to [x], or raise
[Not_found] if no such element exists. *)

should state that the equal is Ord.compare. It does not mean that the
elements are really equal. This could be misleading to users as some
might think they are looking for something they already have in hand (x in find x s).

Maybe:

(** [find x s] returns the element of [s] equal to [x]
(as seen by Ord.compare), or raise [Not_found] if no such element exists. *)

Or something along this line may be better.

@vicuna
Copy link
Author

vicuna commented Jan 8, 2013

Comment author: @alainfrisch

Thanks, I've updated the doc.

@vicuna
Copy link
Author

vicuna commented Jan 11, 2013

Comment author: berenger

I gave a try at the find operation in my software
(some kind of index for many protein structures).

I took the find.ml file from svn trunk and added
it to my software (kind of dirty, but allows
to try the latest version of set.ml without
having to change other things):

when using a Map

2013-01-11 11:34:17.128205+09:00 Info loaded index for 16488403 fragments in 75.458s

when using the new Set with a find operation

2013-01-11 12:17:07.698033+09:00 Info loaded index for 16488403 fragments in 40.898s

That's pretty! :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants