0005864: No find operation in Set

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

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

Relationships