Proposed additions to Data.Map: lookupFloor and lookupCeiling

Hi,  here are two quick, modest additions to Data.Map.   As Map is
exported abstractly,  lookupFlor can't be defined outside the library
except via splitLookup and findMax.   On the other hand,  these
implementations should be nearly the same cost as a regular lookup.

Best,
Leon

-- | /O(log n)/. Find the greatest key that is smaller or equal
-- to the given target key.   This \"floor\" key is returned, along with it's
-- associated value,  as  <at> 'Just' (key, value) <at> .   If the map does not have
-- a key that is smaller or equal to the target key,  then this function
-- returns 'Nothing'.

lookupFloor :: Ord k => k -> Map k a -> Maybe (k,a)
lookupFloor = go Tip
  where
    go s k t
     = case t of
        Tip -> case s of
                 Tip -> Nothing
                 Bin _ ka a _ _ -> Just (ka,a)
        Bin _ ka a l r
            -> case compare ka k of
                 LT -> go t k r
                 GT -> go s k l
                 EQ -> Just (ka,a)

-- | /O(log n)/. Find the smallest key that is greater or equal
-- to the given target key.   This \"ceiling\" key is returned, along with it's

Re: Status of nubOrd (Proposal #2629)

On Wed, Feb 24, 2010 at 3:23 PM, Gwern Branwen <gwern0 <at> gmail.com> wrote:
> nub . sort (and the reverse) are very frequent. The attached sort.txt
> was produced by
>
>    find bin/ -name "*.hs" -exec sh -c "grep sort {} | grep nub && echo
> {}" \; > sort.txt
>
> It's very crude and obviously produces lots of false positives &
> negatives, but even so, there's at least >50 uses of nub . sort etc.

Incidentally,  data-ordlist has a nubSort implementation that's never
more expensive than Data.List.sort.  It's the same mergesort algorithm
provided in Data.List except that it removes duplicates as it merges
the lists.

The library also provides a linear-time nub and nubBy on ordered
lists,  however this implementation is not used as part of nubSort.

http://hackage.haskell.org/package/data-ordlist

Best,
Leon

Re: Proposed additions to Data.Map: lookupFloor and lookupCeiling

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

Re: Proposed additions to Data.Map: lookupFloor and lookupCeiling

On Mon, Mar 1, 2010 at 2:39 AM, Sean Leather <leather <at> cs.uu.nl> wrote:
> It seems more intuitive to reverse the naming. The key parameter to
> lookupFloor is actually the ceiling, and the key returned is the greatest
> key less than or equal to the ceiling. Since there is no floor involved
> here, I would call the function lookupCeiling.

The greatest number less than something would be the floor.  

For example:

ghci>  let map = Map.fromList [ (x, ()) | x <- [0,10..1000] ]
ghci>  lookupFloor 75 map
   Just (70, ())
ghci>  floor 7.5
   7
ghci>  lookupCeiling 115 map
   Just (120,())
ghci>  ceiling 11.5
   12

But honestly I almost invariably get the definitions of floor and
ceiling wrong unless I stop to think for a few seconds.   I've trained
myself to do that.     Maybe a few examples in the haddocks would
be in order.   That's easier to comprehend,  if you know approximately
what it should do.

Also, it occurs to me that maybe a combined function :: (Ord k) => k
-> Map k v -> (Maybe k v, Maybe k v)  would be useful in addition to
or in place of lookupFloor and lookupCeiling.  But I'm not sure.

Best,
Leon

Re: Proposed additions to Data.Map: lookupFloor and lookupCeiling

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

Re: Proposed additions to Data.Map: lookupFloor and lookupCeiling

On Mon, Mar 1, 2010 at 2:34 AM, Sean Leather <leather <at> cs.uu.nl> wrote:
>
> On Mon, Mar 1, 2010 at 09:40, Leon Smith wrote:
>>
>> On Mon, Mar 1, 2010 at 2:39 AM, Sean Leather wrote:
>> > It seems more intuitive to reverse the naming. The key parameter to
>> > lookupFloor is actually the ceiling, and the key returned is the
>> > greatest
>> > key less than or equal to the ceiling. Since there is no floor involved
>> > here, I would call the function lookupCeiling.
>>
>> The greatest number less than something would be the floor.  
>
> So, what I didn't say (but was thinking) was that I would find these
> renamings more intuitive:
>
> lookupFloor --> lookupWithCeiling
> lookupCeiling --> lookupWithFloor

I have these implemented as lookupBelow and lookupAbove.  Perhaps
findBelow and findAbove would be more consistent with findMin findMax.

Mine are implemented as splitLookup followed by (toDescList,
toAscList).  The caller can decide how many they want above and below.

It would be nice to have some discussion of performance or maybe
benchmarks to justify this addition over the more flexible
(toDescList, toAscList) implementation.

As an aside, the Data.Map implementation of split has never been
useful for me because it bizarrely omits the key at the given point.
I've never come across a situation where that would be useful.
splitLookup at least gives it to you, but separately as a Maybe rather
than as the first element of the 'above' map, which is how I always
turn out to want it.

Oh well, too late to change those functions I suppose.

The customary definition of a range is (<x, >=x) or (>=low, <high) but
various haskell libraries don't seem to follow that custom.  Your
version of lookupCeiling wouldn't be too useful to me because I
couldn't use them together to get the values before and after a point.

Re: Status of nubOrd (Proposal #2629)

On Sun, Feb 28, 2010 at 9:39 PM, Leon Smith <leon.p.smith <at> gmail.com> wrote:
> On Wed, Feb 24, 2010 at 3:23 PM, Gwern Branwen <gwern0 <at> gmail.com> wrote:
>> nub . sort (and the reverse) are very frequent. The attached sort.txt
>> was produced by
>>
>>    find bin/ -name "*.hs" -exec sh -c "grep sort {} | grep nub && echo
>> {}" \; > sort.txt
>>
>> It's very crude and obviously produces lots of false positives &
>> negatives, but even so, there's at least >50 uses of nub . sort etc.
>
> Incidentally,  data-ordlist has a nubSort implementation that's never
> more expensive than Data.List.sort.  It's the same mergesort algorithm
> provided in Data.List except that it removes duplicates as it merges
> the lists.

Hm. But sort was recently modified with some tricks from nhc, IIRC. Is
it up to date?

> The library also provides a linear-time nub and nubBy on ordered
> lists,  however this implementation is not used as part of nubSort.
>
> http://hackage.haskell.org/package/data-ordlist
>
> Best,
> Leon

Thanks for the pointers. I briefly looked at data-ordlist during the
searching, but I didn't take the time to figure out what exactly it
was doing.

--

-- 
gwern

Re: Text.PrettyPrint bug or doc bug

Ian Lynagh schrieb:
> On Wed, Feb 24, 2010 at 01:10:38PM +0100, Marcus D. Gabriel wrote:
>> The documentation for Text.PrettyPrint.HughesPJ states
>> that vcat is the "List version of $$", but it works as
>> the list version ($+$).
>>
>> So either the documentation needs to be changed or
>> the code.  It would be nice to have both versions.
> 
Hi,
do you have a actual use case for the "List version of $$" ? It would 
make a good test I suppose.

> It looks like the behaviour changed in
> 
> Tue Jun 24 12:37:15 BST 2008  benedikt.huber <at> gmail.com
>   * fillNB bug, lazy vcat
> 
> i.e. the version that came with GHC 6.10. As it's had the current
> behaviour for some time, it would probably make sense to have a
> library submission to determine what the behaviour should be, and
> whether we want another function for the other behaviour:
>     http://www.haskell.org/haskellwiki/Library_submissions
> 
This is indeed a bug; I've reported it back in December 2008, but 
unfortunately did not file a bug report:

http://www.haskell.org/pipermail/libraries/2008-December/011032.html
(at the end of the message, starting with [1])

Personally I think the "List version of $+$" is more common, but
changing the implementation seems also fine.

It would be nice to solve the other (trickier) issue discussed in the 
mail referenced above as well.

cheers, benedikt

Doc fixes in Control.Exception

Hello,

I noticed some minor errors in the documentation of Control.Exception.
The attached patch fixes them.

It would be nice if somebody could apply the patch.

regards,

Bas

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

Re: Proposed additions to Data.Map: lookupFloor and lookupCeiling

Sean Leather wrote:
>     -- | /O(log n)/. Find the greatest key that is smaller or equal
>     -- to the given target key.   This \"floor\" key is returned,
> 
>     -- | /O(log n)/. Find the smallest key that is greater or equal
>     -- to the given target key.   This \"ceiling\" key is returned,
> 
> It seems more intuitive to reverse the naming. The key parameter to 
> lookupFloor is actually the ceiling, and the key returned is the 
> greatest key less than or equal to the ceiling. Since there is no floor 
> involved here, I would call the function lookupCeiling.

As another point of reference, the Java TreeMap class provides [1]:

   floorKey(K key)
           Returns the greatest key less than or equal to the given key,
             or null if there is no such key.
   ceilingKey(K key)
           Returns the least key greater than or equal to the given key,
             or null if there is no such key.
   higherKey(K key)
           Returns the least key strictly greater than the given key,
             or null if there is no such key.
   lowerKey(K key)
           Returns the greatest key strictly less than the given key,
             or null if there is no such key.

My proposal would be to just call things as they are, and add the functions 
findGreater, findLess, findGreaterEqual and findLessEqual.

Twan

[1] http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html