|Anonymous | Login | Signup for a new account||2019-02-24 07:10 CET|
|Main | My View | View Issues | Change Log | Roadmap|
|View Issue Details|
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0007277||OCaml||standard library||public||2016-06-23 20:21||2016-12-06 16:31|
|Priority||normal||Severity||feature||Reproducibility||have not tried|
|Target Version||4.05.0 +dev/beta1/beta2/beta3/rc1||Fixed in Version||4.05.0 +dev/beta1/beta2/beta3/rc1|
|Summary||0007277: Variants of Map.find|
|Description||I'm suggesting to add the following functions (impl is trivial):|
val find_le : key -> 'a t -> (key * 'a) option * 'a option
val find_ge : key -> 'a t -> 'a option * (key * 'a) option
find_le k m returns a pair where the left component is the binding with the biggest key smaller than k (if existing) and the right component is the value for k (if existing). find_ge symmetrically returns the value for k and the binding with the smallest key bigger than k.
|Additional Information||We can of course already do that with Map.split, but in this case the submaps are constructed which may be expensive. So the motivation is performance.|
Use case: Imagine you need a mapping where the keys are disjoint ranges (left,right), and you want to implement a function that returns the mapped value for any number in that range. With find_le you can do that by only putting the left points of the ranges into the map (and an additional member check).
Alternatives: The API could be a little bit "smaller" (not returning the exact match):
val find_lt : key -> 'a t -> (key * 'a) option
val find_gt : key -> 'a t -> (key * 'a) option
Or it could be "bigger" (always returning the previous and the next elements):
val find_around : key -> 'a t -> (key * 'a) option * 'a option * (key * 'a) option
IMHO, this is matter of taste. The use case I know wouldn't profit from find_around.
I'll happily submit a PR when the addition is accepted (and the style has been agreed upon).
|Tags||No tags attached.|
|Attached Files||find_around.ml [^] (1,475 bytes) 2016-06-27 12:57 [Show Content]|
I'm concerned by the number of small variants around the proposal that would all look as useful (e.g. find_lt, find_lte, ...). Since performance is the key reason here, the most general form (find_around) might not be enough (but still sometimes useful, since it would be more efficient than multiple calls to simple functions).
Gerd: in your case, would find_lt/find_gt be enough?
A slightly more general interface would be:
val find_first: (key -> bool) -> 'a t -> (key * 'a) option
val find_last: (key -> bool) -> 'a t -> (key * 'a) option
where the predicate is assumed to be monotonic. From these function, one can create find_lt/find_gt, but also variants with non-strict comparison (find_lte/find_gte), and the overhead could be acceptable.
Well, the interface design would be a little bit simpler if flambda could optimize the unused parts of find_around away. However, to my understanding flambda cannot do this (you need to optimize the whole recursion, and track unused values through it - can somebody verify? - I've attached a sample impl of find_around).
Sure, find_lt/find_gt would be good enough for my application, i.e. a one-sided function. There is still the question where to return an option or whether to raise Not_found. The latter would be more consistent with the existing interface.
find_first/last is also a nice idea (and would solve my problem).
I like Alain's proposal, as it reminds my of Dedekind cuts, and after a bit reflection I realised that it extends the interface beyond the four possible inequalities:
To use `find_lt` and `find_gt` one needs to make up a suitable key. This key is not necessarily easy to construct for complex types. Moreover, the key does not necessarily exist. For instance, if the keys of the map are multi-precision fractions, then `field_first` would allow us to find the first binding after a transcendental number, while there is no fraction we could pass to `find_gt` which would guarantee the right result.
|Submitted a PR: https://github.com/ocaml/ocaml/pull/665 [^]|
|2016-06-23 20:21||gerd||New Issue|
|2016-06-27 11:36||frisch||Note Added: 0015999|
|2016-06-27 12:57||gerd||File Added: find_around.ml|
|2016-06-27 13:03||gerd||Note Added: 0016000|
|2016-07-05 23:11||paurkedal||Note Added: 0016038|
|2016-07-06 14:39||gerd||Note Added: 0016041|
|2016-09-07 17:01||shinwell||Target Version||=> 4.05.0 +dev/beta1/beta2/beta3/rc1|
|2016-12-06 16:31||frisch||Note Added: 0016647|
|2016-12-06 16:31||frisch||Status||new => resolved|
|2016-12-06 16:31||frisch||Fixed in Version||=> 4.05.0 +dev/beta1/beta2/beta3/rc1|
|2016-12-06 16:31||frisch||Resolution||open => fixed|
|2016-12-06 16:31||frisch||Assigned To||=> frisch|
|2017-02-23 16:43||doligez||Category||OCaml standard library => standard library|
|Copyright © 2000 - 2011 MantisBT Group|