Minor containers API changes
wren ng thornton
wren at freegeek.org
Tue Nov 29 01:36:33 CET 2011
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:
> 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):
>> 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
>> `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).
More information about the Libraries