Minor containers API changes

Evan Laforge qdunkan at gmail.com
Mon Nov 28 21:35:53 CET 2011

[ sorry, somehow gmail forgot about my default reply-to-all config ]

> 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.

I've used mapKeys a bit, but if the performance is really the same as
'Map.fromList . map first f . Map.toList' then I guess it's not super
necessary.  On the other hand, I would just immediately add the above
composition to my own
Map utils module, and why should we go removing stuff if it's just
going to cause people to add copies to their private libraries?

> 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 actually added toDescList so I do have an opinion.  I couldn't
figure out any way it could be expressed as a left fold (or maybe that
left fold function didn't exist back then).  Without this function
there's no way to (efficiently) iterate over a map backwards, which is
pretty essential for an ordered collection!

In any case, it's asymmetrical to have toAscList but no toDescList.

+1 on everything else!

More information about the Libraries mailing list