Proposed additions to Data.Map: lookupFloor and lookupCeiling

[wren ng thornton]

Leon Smith wrote:
> On Mon, Mar 1, 2010 at 5:34 AM, Sean Leather <leather at cs.uu.nl> wrote:
>> I understand where you're coming from. You're mapping the set of keys to the
>> set of integers and applying the (e.g.) floor function to the key within
>> that set. Alternative (though verbose) names for your functions might be:
>>
>> lookupFloor --> applyFloorAndLookup
>> lookupCeiling --> applyCeilingAndLookup
>>
>> In contrast, I looked at the parameter as being the lower or upper bound.
>> So, perhaps an even better naming (from my point of view) would be:
>>
>> lookupFloor --> lookupWithUpperBound or lookupUpperBound or lookupUB or ...
>> lookupCeiling --> lookupWithLowerBound or lookupLowerBound or lookupLB or
>> ...
>>
> 
> Ok,  I think I now see where you are coming from,  but I don't agree.
>  We are trying to find the relationship between many keys in a map to
> one target key,   so there is only one direction in which the standard
> definitions of "floor" and "ceiling" make sense.


What is the floor/ceiling? That is, when we use a notation x = fl(y) or 
x = cl(y), which of x and y is the floor/ceiling?

One way of looking at it is that the y we pass in is the boundary and 
the x is the closest thing to it. Then, y is the floor/ceiling since 
it's the boundary.

Another way of looking at it is that we pass in something that's no good 
(because it's not an integer, or there's no value for that key), and we 
get back the nearest thing that is good. Then, x is the floor/ceiling 
because its the nearest thing to our no-good intermediate value.

Both views make sense in their own way. The latter is the perspective 
used for taking the integer floor/ceiling of reals. The former surely 
has some analogues in topology or limit series. Personally, I think it'd 
give less potential for confusion to avoid either interpretation and 
just use names like "lookupAbove" to mean getting the (k,v) pair for the 
least k above the query, and analogously for "lookupBelow".

-- 
Live well,
~wren