Re: Minor containers API changes

On 11/30/11 7:51 AM, Felipe Almeida Lessa wrote:

On Wed, Nov 30, 2011 at 4:54 AM, 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