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