Minor containers API changes

[Kazu Yamamoto ( 山本和彦 )]

Hello,

This is off-topic but I'm curious.

Why the container package does not provide a type-class to unify APIs?
Are there any technical/historical reasons?

--Kazu

> Hi everyone,
> 
> I have several containers API changes propositions.
> 
> First five are an attempt to unify the API of different structures. The
> documentation states IntMap is Map replacement and IntSet is Set
> replacement, but there are several shortcomings:
> 
> 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
> 
>    I vote for (b), because (a) could cause unexpected runtime errors.
>    Additionally, I expect very little programs depend on
>    `{IntMap,IntSet}.deleteMin empty` causing runtime error.
> 
> 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
> 
>    I vote for (b), because it generalizes the original functionality.
> 
> 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.
> 
> 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.
> 
> 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 have no strong opinion here. The `toDescList` can be trivially
>    expressed as left fold. But it is currently a subject to list fusion.
>    To vote for (a).
> 
> 
> Several other changes follow:
> 
> 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).
> 
>    Cons: fromSet is a trivial composition:
>            fromSet f = Map.fromDistinctAscList . map (\k -> (k, f k)) . Set.toAscList
>          This can be defined by the user and is asymptotically optimal.
>    Pro: performance. Also the performance of keysSet would improve, if
>         the map can use data constructors of set.
> 
>    I vote for adding these methods.
> 
> 7) Improve the generality of intersectionWith.
>    Currently the Map and IntMap define
>      intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
>      intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
> 
>    But the combining function is not general enough. Consider two
>    IntMaps storing hashable elements as (hash(element), element).
>    When intersecting elements with the same hash, the intersection can
>    be empty.
> 
>    I propose to change the type of these methods to
>      intersectionWith :: Ord k => (a -> b -> Maybe c) -> Map k a -> Map k b -> Map k c
>      intersectionWithKey :: Ord k => (k -> a -> b -> Maybe c) -> Map k a -> Map k b -> Map k c
>    (and appropriately for IntMap).
> 
>    Note that the combining function of differenceWith already has type `(a -> b -> Maybe a)`.
> 
> 
> Discussion period: 2 weeks
> 
> Cheers,
> Milan
> 
> PS: Sorry for the long email.
> 
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries