Proposed additions to Data.Map: lookupFloor and lookupCeiling

Yitzchak Gale gale at
Tue Mar 2 09:56:56 EST 2010

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.

Here are some ideas of what to do about it:

1. Define all 42 of these functions in a separate module.
(This has the pleasant advantage of giving us a new
bikeshed to paint to name this new module. What fun!)

2. Get rid of all of the functions except just one that is
general enough to provide all of the others as a special
case. Add copious documentation, with many clear examples,
so that anyone can get whatever they need without having
to think too much.

The general function might have a type something like:

data Extremality = Min | Max | Greater | Less |
  GreaterEqual | LessEqual

Extremality -> (k -> a -> Maybe a) -> Map k a -> Maybe ((k, a), Map k a)

2'. As a variation on (2), we could, in addition to the general function,
leave in the most commonly used functions in their simple form.
(Which ones? Woohoo, more bikesheds!)

3. Use type trickery to construct a single interface that provides
each of the possibilities. So that you could write something like

update greater withKey

and get the function you want. This one is the most fun to write,
even though we probably won't end up using it.


More information about the Libraries mailing list