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
Comments
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. |
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 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. |
Comment author: berenger hcarty is right: my use case is exactly of this kind. |
Comment author: berenger This might be the code for set.ml. let rec find x = function |
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? |
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. |
Comment author: berenger If I send a patch with the code, is there a chance it would be accepted? |
Comment author: @alainfrisch No need for a patch, I've committed your implementation (commit 13211 on trunk). |
Comment author: berenger Wow, nice. Maybe the ocamldoc: (** [find x s] returns the element of [s] equal to [x], or raise should state that the equal is Ord.compare. It does not mean that the Maybe: (** [find x s] returns the element of [s] equal to [x] Or something along this line may be better. |
Comment author: @alainfrisch Thanks, I've updated the doc. |
Comment author: berenger I gave a try at the find operation in my software I took the find.ml file from svn trunk and added when using a Map2013-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 operation2013-01-11 12:17:07.698033+09:00 Info loaded index for 16488403 fragments in 40.898s That's pretty! :) |
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.
The text was updated successfully, but these errors were encountered: