Proposed additions to Data.Map: lookupFloor and lookupCeiling

[Evan Laforge]

On Mon, Mar 1, 2010 at 2:34 AM, Sean Leather <leather at cs.uu.nl> wrote:
>
> On Mon, Mar 1, 2010 at 09:40, Leon Smith wrote:
>>
>> On Mon, Mar 1, 2010 at 2:39 AM, Sean Leather wrote:
>> > It seems more intuitive to reverse the naming. The key parameter to
>> > lookupFloor is actually the ceiling, and the key returned is the
>> > greatest
>> > key less than or equal to the ceiling. Since there is no floor involved
>> > here, I would call the function lookupCeiling.
>>
>> The greatest number less than something would be the floor.  :-)
>
> So, what I didn't say (but was thinking) was that I would find these
> renamings more intuitive:
>
> lookupFloor --> lookupWithCeiling
> lookupCeiling --> lookupWithFloor

I have these implemented as lookupBelow and lookupAbove.  Perhaps
findBelow and findAbove would be more consistent with findMin findMax.

Mine are implemented as splitLookup followed by (toDescList,
toAscList).  The caller can decide how many they want above and below.

It would be nice to have some discussion of performance or maybe
benchmarks to justify this addition over the more flexible
(toDescList, toAscList) implementation.

As an aside, the Data.Map implementation of split has never been
useful for me because it bizarrely omits the key at the given point.
I've never come across a situation where that would be useful.
splitLookup at least gives it to you, but separately as a Maybe rather
than as the first element of the 'above' map, which is how I always
turn out to want it.

Oh well, too late to change those functions I suppose.

The customary definition of a range is (<x, >=x) or (>=low, <high) but
various haskell libraries don't seem to follow that custom.  Your
version of lookupCeiling wouldn't be too useful to me because I
couldn't use them together to get the values before and after a point.