Minor containers API changes

[wren ng thornton]

I agree entirely with Joachim Breitner: +1 in general, but I'm opposed 
to removing/deprecating functions which (a) allow for list fusion, (b) 
allow for other significant optimizations, or (c) which clearly express 
the intent behind common idioms.


On 11/28/11 3:24 PM, Joachim Breitner wrote:
> Hi,
>
> I’ll skip on the +1 and only make negative comments, as they are
> fewer :-)
>
> Am Montag, den 28.11.2011, 17:28 +0100 schrieb Milan Straka:
>> 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.
>
> They seem useful to me to write legible code, therefore I’m in favor of
> (b). Also, they are used in the wild (random reference):
> http://darcswatch.nomeata.de/bundles/a3fbac8e4ce65d1426c5d1e0d19a6020f425b5d2.dpatch
>
>
>> 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).
>
> I have at least one project where I make heavy use of list fusion. In
> that case I only use toList, but one could imagine a case where I want
> that order. Therefore, I’m in favor of (b).
>
>> 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.
>
> I very much agree (guess I don’t want to be only negative after all).

-- 
Live well,
~wren