[Haskell-cafe] Data.Map.fromListWith

[Paul Johnson]

Alexander Dunlap wrote:
> 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.
Ahh yes.  I was thinking that the job of fromListWith was analogous to 
foldr, but carrying out the fold on a per-key basis.  However I see now 
that it is more like  foldr1 than foldr because foldr needs a zero value.

So we could have

   fromListWithZero :: Ord k => (a -> b -> b) -> b -> [(k, a)] -> Map k b
   fromListWithZero combiner zero pairs = ...

The first time a key is seen the combining function is called with 
"zero" as its second argument.  E.g.

   fromListWithZero (:) [] xs

Or is that too much trouble?  Accumulating a collection of lists is the 
most obvious use of this function, and you can do that already (albeit 
rather clunkily) with

   fromListWith (++) $ map (\(k,v) -> (k, [v]) $ xs

The only time that fromListWithZero would be especially useful is when 
you want the fold to be eager.

Paul.