Proposed additions to Data.Map: lookupFloor and lookupCeiling

[Yitzchak Gale]

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

Leon Smith wrote:
> I find these names acceptable, although I would honestly prefer
> something like "findFloor" or "lookupFloor"

Why?

> 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)

All of those approaches have the same asymptotic behavior.
The question is, how many different functions do we need
in this library to improve the coefficient in various special cases?

Now that I have become aware of the feature creep that is
affecting this library, I am opposed to adding these functions.
Enough is enough.

But here's another idea: put the internal workings into a separate
module called Data.Map.Internals that exports everything,
and have Data.Map re-export only the stable public API.

This way, people are free to upload to Hackage their own
creative ways of using Data.Map more efficiently.
And we can tighten up the public interface to be leaner
and meaner, without depriving people of the ability
to tweak down those coefficients when they need to.

Regards,
Yitz