Minor containers API changes

[wren ng thornton]

On 11/30/11 1:54 AM, Liyang HU wrote:
> Evan Laforge<qdunkan<at>  gmail.com>  writes:
>>> 5) `toDescList` exists in Map, but not in IntMap, Set or IntSet.
>> Without this function
>> there's no way to (efficiently) iterate over a map backwards, which is
>> pretty essential for an ordered collection!
>
> How about using the Down/Dual/Desc/Converse/Opposite/Reverse newtype discussed
> in another recent thread, and providing for Data.Map:
>
>    reverse :: Map k a ->  Map (Reverse k) a
>    reverse Tip = Tip
>    reverse (Bin n k a l r) = Bin n (Reverse k) a (reverse r) (reverse l)
>
> (Arguably we also need reverse' :: Map (Reverse k) a ->  Map k a. Hmm...)

That'd be a nice function once the Ord-reversing newtype is included, 
but I worry about API explosion. As you mention, we'd want both reverse 
and unreverse.

However, this does suggest a very valuable extension to the API. Namely, 
we have mapKeysMonotonic but we lack the dual version:

     mapKeysAntitonic :: (k1 -> k1) -> Map k1 a -> Map k2 a
     mapKeysAntitonic f Tip = Tip
     mapKeysAntitonic f (Bin n k a l r)
         = Bin n (f k) a (mapKeysAntitonic f r) (mapKeysAntitonic f l)

With that function users could just define (or use inline),

     -- assuming newtype Reverse a = Reverse { unReverse :: a }

     reverse :: Map k a -> Map (Reverse k) a
     reverse = mapKeysAntitonic Reverse

     unreverse :: Map (Reverse k) a -> Map k a
     unreverse = mapKeysAntitonic unReverse

But this way we only add one function to the API, and that function is 
very general since it can be used with any antitone function. I'm 
surprise we've never noticed the lack of mapKeysAntitonic before!

-- 
Live well,
~wren