Minor containers API changes

[wren ng thornton]

On 11/30/11 7:51 AM, Felipe Almeida Lessa wrote:
> On Wed, Nov 30, 2011 at 4:54 AM, Liyang HU<haskell.org at liyang.hu>  wrote:
>> 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...)
>
>    reverse' :: Map (Reverse k) a ->  Map k a
>    reverse' = unsafeCoerce . reverse
>
> Sorry, couldn't resist =).

As an addendum to the mapKeysAntitonic proposal, we should add the 
functorial rewrite rules which account for mono-/antitonicity.

     {-# RULES
         "mapKeysAntitonic id"
             mapKeysAntitonic id = id

         "mapKeysAntitonic f . mapKeysAntitonic g"
             mapKeysAntitonic f . mapKeysAntitonic g
                 = mapKeysMonotonic (f . g)

         "mapKeysAntitonic f / mapKeysAntitonic g"
             forall x.
                 mapKeysAntitonic f (mapKeysAntitonic g x)
                     = mapKeysMonotonic (f . g) x

         -- And if these aren't already declared:
         "mapKeysMonotonic id"
             mapKeysMonotonic id = id

         "mapKeysMonotonic f . mapKeysMonotonic g"
             mapKeysMonotonic f . mapKeysMonotonic g
                 = mapKeysMonotonic (f . g)

         "mapKeysMonotonic f / mapKeysMonotonic g"
             forall x.
                 mapKeysMonotonic f (mapKeysMonotonic g x)
                     = mapKeysMonotonic (f . g) x
     #-}

 From there, it should be easy for GHC to do reversal fusion:

     mapKeysAntitonic Reverse . mapKeysAntitonic unReverse
     ===
     mapKeysMonotonic (Reverse . unReverse)
     ===
     mapKeysMonotonic id
     ===
     id

     mapKeysAntitonic unReverse . mapKeysAntitonic Reverse
     ===
     mapKeysMonotonic (unReverse . Reverse)
     ===
     mapKeysMonotonic id
     ===
     id

Or, more generally, fusion of any pair of inverse antitonic functions. 
Though for things other than newtypes it may require stating a rule that 
the functions are indeed inverses.

This way, not only can we avoid unsafeCoerce (which can impede 
optimizations), but we get some optimizations to boot!

-- 
Live well,
~wren