Proposal: add 'findLess' and variants to containers

[Twan van Laarhoven]

On 2012-02-18 00:51, Johan Tibell wrote:
 > Lets settle on the names. I
 > currently dislike that we have 'lookup' and 'findDefault' (which is
 > lookup with a default value.) We should agree on a principle for when
 > we use the two words.

With regards to 'lookup' vs 'find': the current convention seems to be that 
lookup* returns 'Maybe a', while find* returns 'a'. Compare for example 
'lookupIndex' and 'findIndex'.

That means that the proposed functions should be called 'lookupLess', etc.


On 2012-02-18 11:46, Milan Straka wrote:
> At some point I thought maybe we could add just these two functions:
>
>    predecessor :: Ord a =>  a ->  Set a ->  Maybe a
>    successor :: Ord a =>  a ->  Set a ->  Maybe a
>
> These functions work like findLess, findGreater, i.e., they return
> a strict predecessor or successor of a given key. The key does not need
> to exist in the set/map.

The terms successor and predecessor make some sense for Set, but less for a Map. 
IMO, a name like findGreater makes the intent much clearer.

> Are there any good use cases for findLessEqual/findGreaterEqual,
> instead of calling lookup and if it fails, call predecessor/successor?

Such a two-tier lookup would be two times as slow, and also inconvenient for the 
user of the library. With this argument we should also get rid of, for example, 
one of 'isSubmapOf' and 'isProperSubmapOf'.

Here is a simple use case: suppose that you have some boxes, Set Size, and want 
to find the smallest box that will fit a certain item. The natural thing to do 
would be 'findGreaterEqual itemSize boxes'.

If the sizes are integers, you could do 'findGreater (itemSize-1) boxes'. But 
that makes the intent of the code less clear, and makes it easier to introduce 
bugs. This trick also fails when sizes are not integers.


Twan