Re: [Haskell-cafe] Data.Map.fromListWith

On Sat, Dec 6, 2008 at 12:22 PM, Paul Johnson 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%3... k => (a -> a -> a) -> [(k, a)] -> Map http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.ht... 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%3... k => (a -> b -> b) -> [(k, a)] -> Map http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.ht... 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

Alexander Dunlap wrote: 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.