Proposed additions to Data.Map: lookupFloor and lookupCeiling

[Leon Smith]

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.


On Mon, Mar 1, 2010 at 9:24 PM, Twan van Laarhoven <twanvl at gmail.com> wrote:
> As another point of reference, the Java TreeMap class provides [1]:
>
>  floorKey(K key)
>          Returns the greatest key less than or equal to the given key,
>            or null if there is no such key.
>  ceilingKey(K key)
>          Returns the least key greater than or equal to the given key,
>            or null if there is no such key.
>  higherKey(K key)
>          Returns the least key strictly greater than the given key,
>            or null if there is no such key.
>  lowerKey(K key)
>          Returns the greatest key strictly less than the given key,
>            or null if there is no such key.

This is interesting,  because I don't recall ever seeing these
functions with "floor" and "ceiling" in their name.   So this would be
a case of convergent evolution.

> My proposal would be to just call things as they are, and add the functions
> findGreater, findLess, findGreaterEqual and findLessEqual.

I find these names acceptable, although I would honestly prefer
something like "findFloor" or "lookupFloor"



On Tue, Mar 2, 2010 at 9:56 AM, Yitzchak Gale <gale at sefer.org> wrote:
> Twan van Laarhoven wrote:
>> My proposal would be to just call things as they are, and add the functions
>> findGreater, findLess, findGreaterEqual and findLessEqual.
>
> I vote for that proposal.
>
> I hate adding functions to our libraries. But if we are adding these,
> we probably also need to add:
>
> deleteGreater, deleteLess, deleteGreaterEqual, deleteLessEqual
>
> Those common operations are also much more expensive when
> done from outside the library.
>
> Wait - horrors! I hadn't looked at the library lately. We now have,
> for each of Min and Max:
>
> find, delete, deleteFind, update, updateWithKey,
> view, viewWithKey
>
> For consistency, we would need to add each of those seven
> for each of the new comparisons - 28 new functions, for a
> total of 42! We have finally discovered the Answer to the
> Ultimate Question of Life, the Universe, and Everything.
>
> Why did someone have to add all of those functions to
> begin with? Look what bloat it's causing.

Of course, this is the balancing act that every library writer has to manage.

However,  I think that it's likely that a simple "findFloor" will be
sufficient to reasonably cover all these possibilities.   It's just
two passes over the tree,  one to find the floor key,  and a second to
do a deletion or whatever.    This is better than using splitLookup
and findMax to find the floor key,  as this combination involves more
memory allocation and more complicated data structure transformations.
  (whereas lookupFloor involves no changes to the data structure,
although it might force something that hadn't been forced before)


Best,
Leon