Minor containers API changes

[Liyang HU]

Milan Straka <fox <at> ucw.cz> writes:
> 1) `{Map,Set}.deleteMin empty` return `empty`
>    `{IntMap,IntSet}.deleteMin empty` trigger `error "Cannot delete in 
empty..."`
> 
>    Solutions: (a) make `{Map,Set}.deleteMin empty` throw error
>               (b) make `{IntMap,IntSet}.deleteMin empty` return empty

+1 for (b)

> 2) `Map.deleteFind{Min,Max}` has type `Map k a -> ((k,a),Map k a)`
>    `IntMap.deleteFind{Min,Max}` has type `IntMap a -> (a, IntMap a)`
> 
>    Solutions: (a) make the Map variant return only values
>               (b) make the IntMap variant return both key and value

+1 for (b)

> 3) `Map.update{Min,Max}` is given a function of type `(a -> Maybe a)`
>    `Map.update{Min,Max}WithKey` is given a function of type `(key -> a -> 
Maybe a)`
>    `IntMap.update{Min,Max}` is given a function of type `(a -> a)`
>    `IntMap.update{Min,Max}WithKey` is given a function of type `(key -> a -> 
a)`
> 
>    Solutions: (a) the Map variants would get a function of type `[key -> ] a -
> a`
>               (b) the IntMap variants would get a function of type `[key -> ] 
a -> Maybe a`
> 
>    I vote for (b), because it generalizes the original functionality.

+1 for (b)

> 4) The functions
>    `mapKeys :: Ord k2 => (k1->k2) -> Map k1 a -> Map k2 a`
>    `mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1->k2) -> Map k1 a -> Map k2 
a`
>    `mapKeysMonotonic :: (k1->k2) -> Map k1 a -> Map k2 a`
>    have no IntMap correspondents.  Both `mapKeys` and `mapKeysWith`
>    can be defined by the user without loss of performance.
> 
>    Solutions: (a) deprecate the `mapKeys*` methods from Map
>               (b) add the `mapKeys*` methods to IntMap.
> 
>    I vote for (a). These methods are all trivial compositions and all
>    but all mapKeysMonotonic are defined as such. For mapKeysMonotonic,
>    a trivial composition with the same asymptotic complexity exists.
>    Also, if these were added to IntMap, none of them would have better
>    performance then user-defined methods.

+1 for (b)

Same asymptotic complexity is fine in theory but not necessarily in practice. 
OTOH, API uniformity between Map and IntMap (and HashMap) would be nice, such 
that the only difference would be in the class constraints.

(When Johan adds Data.Map.Class &c., we should rename Map to OrdMap...)

> 5) `toDescList` exists in Map, but not in IntMap, Set or IntSet.
> 
>    Solutions: (a) deprecate `Map.toDescList`
>               (b) add `toDescList` to IntMap. In this case, we should
>                   consider adding it also to Set and IntSet.

I'm inclined towards (a), because if you're going down the route of offering 
Desc versions of toList, why not fromDescList* too?

In fact, deprecate Map.toAscList too, and rename it to Map.toList.

> 6) Result of discussion around http://hackage.haskell.org/trac/ghc/ticket/5242
>    Add
>      `Map.fromSet :: (key -> a) -> Set key -> Map key a`
>      `IntMap.fromSet :: (Int -> a) -> IntSet -> IntMap a`
>    The implementation would exploit same structure of map and set
>    (leave the shape of the original tree/trie, just adding values).

Opting out due to conflict of interests.

> 7) Improve the generality of intersectionWith.

+1

Cheers,
/Liyang