Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005864OCamlOCaml standard librarypublic2012-12-26 03:532013-01-11 04:24
Reporterberenger 
Assigned Tofrisch 
PrioritynormalSeverityfeatureReproducibilityN/A
StatusresolvedResolutionfixed 
PlatformAllOSAllOS VersionAll
Product Version4.00.0 
Target VersionFixed in Version4.01.0+dev 
Summary0005864: No find operation in Set
DescriptionI 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.
TagsNo tags attached.
Attached Files

- Relationships

-  Notes
(0008663)
meyer (developer)
2012-12-29 06:02

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.
(0008666)
hcarty (reporter)
2012-12-29 15:55

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.
(0008687)
berenger (reporter)
2013-01-04 01:41

hcarty is right: my use case is exactly of this kind.
(0008688)
berenger (reporter)
2013-01-04 08:19

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)
(0008691)
thelema (reporter)
2013-01-04 14:20

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?
(0008696)
frisch (developer)
2013-01-05 11:15

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.
(0008703)
berenger (reporter)
2013-01-08 03:05

If I send a patch with the code, is there a chance it would be accepted?
(0008704)
frisch (developer)
2013-01-08 10:01

No need for a patch, I've committed your implementation (commit 13211 on trunk).
(0008705)
berenger (reporter)
2013-01-08 10:25

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.
(0008706)
frisch (developer)
2013-01-08 10:33

Thanks, I've updated the doc.
(0008738)
berenger (reporter)
2013-01-11 04:24

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! :)

- Issue History
Date Modified Username Field Change
2012-12-26 03:53 berenger New Issue
2012-12-29 06:02 meyer Note Added: 0008663
2012-12-29 15:55 hcarty Note Added: 0008666
2013-01-04 01:41 berenger Note Added: 0008687
2013-01-04 08:19 berenger Note Added: 0008688
2013-01-04 14:20 thelema Note Added: 0008691
2013-01-04 15:25 doligez Status new => acknowledged
2013-01-05 11:15 frisch Note Added: 0008696
2013-01-08 03:05 berenger Note Added: 0008703
2013-01-08 10:01 frisch Note Added: 0008704
2013-01-08 10:01 frisch Status acknowledged => resolved
2013-01-08 10:01 frisch Resolution open => fixed
2013-01-08 10:01 frisch Assigned To => frisch
2013-01-08 10:01 frisch Fixed in Version => 4.01.0+dev
2013-01-08 10:25 berenger Note Added: 0008705
2013-01-08 10:33 frisch Note Added: 0008706
2013-01-11 04:24 berenger Note Added: 0008738


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker