Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0007277OCamlstandard librarypublic2016-06-23 20:212016-12-06 16:31
Assigned Tofrisch 
PrioritynormalSeverityfeatureReproducibilityhave not tried
PlatformOSOS Version
Product Version4.03.0 
Target Version4.05.0 +dev/beta1/beta2/beta3/rc1Fixed in Version4.05.0 +dev/beta1/beta2/beta3/rc1 
Summary0007277: Variants of Map.find
DescriptionI'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 InformationWe 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).
TagsNo tags attached.
Attached Files? file icon [^] (1,475 bytes) 2016-06-27 12:57 [Show Content]

- Relationships

-  Notes
frisch (developer)
2016-06-27 11:36

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.
gerd (reporter)
2016-06-27 13:03

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).
paurkedal (reporter)
2016-07-05 23:11

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.
gerd (reporter)
2016-07-06 14:39

Submitted a PR: [^]
frisch (developer)
2016-12-06 16:31 [^]

- Issue History
Date Modified Username Field Change
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:
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
Powered by Mantis Bugtracker