[Haskell-cafe] Data.Map.fromListWith

[Alexander Dunlap]

On Sat, Dec 6, 2008 at 12:22 PM, Paul Johnson <paul at cogito.org.uk> wrote:
> I've just been looking at the Data.Map function "fromListWith".  According
> to the docs, it has the type:
>
> *   fromListWith* :: Ord
> <http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Ord.html#t%3AOrd>
> k => (a -> a -> a) -> [(k, a)] -> Map
> <http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.html#t%3AMap>
> k a
>
> I'd have thought that a better type would be
>
> *   fromListWith* :: Ord
> <http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Ord.html#t%3AOrd>
> k => (a -> b -> b) -> [(k, a)] -> Map
> <http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.html#t%3AMap>
> k b
>
> This wouldn't break any existing code, but would allow things like
> "fromListWith (:)" to do the Right Thing.
>
> Would this be a sensible change (along with the other "with" functions in
> the module).
>
> Paul.
>

Hi,

I don't think that type makes sense. fromListWith takes a list of
[(key,value)] and a combining function to combine the values when
there are multiple pairs with the same key. Thus, a type of (a -> b ->
b) for the combining function doesn't make sense because the values
are all going to have the same type (i.e. they are all "a"s). We might
consider (a -> a -> b), but this doesn't make sense either because
then you have some values with type "a" (the ones that didn't need to
be combined) and some with type "b" (the ones that were combined). (a
-> a -> a) is really the only type that works.

I don't think fromListWith (:) makes sense either. (:) :: a -> [a] ->
[a], so you would end up with some values of the map as individual
items and others as lists of items. All of the values need to have the
same type.

Regards,
Alex