Proposal: add 'findLess' and variants to containers

12 Feb 2012

      Hello all,

== Overview ==

I have several times needed functions to find items less than a given key in a 
container. So I propose we add these to the containers library:

     -- | /O(log n)/.
     --   Find the largest element in the set that is @<@ the query.
     findLess :: Ord a => a -> Set a -> Maybe a
     -- | /O(log n)/.
     --   Find the largest element in the set that is @<=@ the query.
     findLessEqual :: Ord a => a -> Set a -> Maybe a
     -- | /O(log n)/.
     --   Find the smallest element in the set that is @>@ the query.
     findGreater :: Ord a => a -> Set a -> Maybe a
     -- | /O(log n)/.
     --   Find the smallest element in the set that is @>=@ the query.
     findGreaterEqual :: Ord a => a -> Set a -> Maybe a

And for Maps:

     findLess, findLessEqual, findGreater, findGreaterEqual
        :: Ord a => a -> Map a b -> Maybe (a,b)

As well as the equivalent functions for IntSet and IntMap.

== Previous proposal and related functions ==

There was a previous proposal to add such functions about two years ago [1]. 
That proposal died due to concerns over adding related 'delete' and 'update' 
functions, and that the API would become too large.

I think the 'find' functions should be added regardless of whether we also add 
'update' and 'delete' variants. On the other hand, for consitency it would be 
better to also add 'deleteLess', etc.

We should perhaps mimic the findMin/findMax functions. The only issue with that 
idea is that findMin does not return a Maybe, but rather fails for an empty 
container. I think that not returning its result in a Maybe would make the 
findLess useless in practice, since there is no such easy precondition for findLess.

As for the API size: This proposal would add a lot of functions to Data.Map and 
Data.Set (especially when we also include 'update' and 'delete' variants). 
However, the mental burden of these new functions is not so large. Library users 
already know what 'find', 'update' and 'delete' mean. Moreover, there is a nice 
symmetry between the 4 different conditions, which means that you can almost 
think of them as one thing.

== Bikeshedding / naming ==

There are several possible names for these functions:
   1. findLess / findLessEqual / findGreater / findGreaterEqual
   2. findMaxLT / findMaxLE / findMinGT / findMinGE
   3. findLower / findFloor / findHigher / findCeiling

I personally prefer either 1 or 2. To me option 3 (which Java uses) is very 
confusing.

== Implementation ==

These functions can be implemented in terms of split, but it is a pain (and 
error prone) to do so:

     findLess         a m = findMax' (fst (split a m))
     findLessEqual    a m = case splitLookup a s of
                              (_,Just b,_)   -> Just (a,b)
                              (m',Nothing,_) -> findMax' m'
     findGreater      a m = findMin' (snd (split a m))
     findGreaterEqual a m = case splitLookup a m of
                              (_,Just b,_)   -> Just (a,b)
                              (_,Nothing,m') -> findMin' m'

where

     findMin' = fmap fst . minViewWithKey
     findMax' = fmap fst . maxViewWithKey

This is really something that shouldn't have to be done by users of the library. 
And we might also be able to come up with a more efficient implementation.

== Discussion period ==

Discussion deadline: 2 weeks from now; Sunday, 26 February 2012.

Twan

[1] http://www.haskell.org/pipermail/libraries/2010-February/013060.html
      continued here:
     http://www.haskell.org/pipermail/libraries/2010-March/013062.html

Twan van Laarhoven

Johan Tibell

Michael Craig

Twan van Laarhoven

Twan van Laarhoven

Johan Tibell

Milan Straka

Twan van Laarhoven

Henning Thielemann

Twan van Laarhoven

Johan Tibell

Thomas Schilling

David Waern

wren ng thornton

Milan Straka

Henning Thielemann

wren ng thornton

Isaac Dupree

tags

participants (9)