Re: Minor containers API changes

On 11/30/11 1:54 AM, Liyang HU wrote:

Evan Laforge 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