Lauri Alanko wrote:
On Mon, May 07, 2007 at 10:23:24AM +0100, Adrian Hey wrote:
instance (Ord k) => Monoid (Map k v) where mempty = empty mappend = union mconcat = unions
This worries me because there is no obviously correct choice for the semantics of union for maps (as in which maps associated values get dropped).
Right. I think that the real fundamental MMap type should be something like:
instance (Ord k, Monoid v) => Monoid (MMap k v) where mempty = empty mappend = unionWith mappend
Ross Paterson has suggested the same thing so I'll go with that, unless Jean-Philippe has some objection (I think Data.Map and Data.Map.AVL should be the same in this regard). This still breaks the Coolections module though, but I guess it's fixable.
and with a lookup operation
lookup :: (Ord k, Monoid v) => k -> MMap k v -> v
which returns mempty when the key was not found in the map, _or_ if a mempty value was somehow stored in the map. The distinction is purely an implementation detail and shouldn't be visible.
Then it is easy to see that the current Data.Map is just a wrapper to the above interface specialized to a left-biased monoid on Maybe. So Data.Map isn't as general as it should be, but at least it's _consistently_ non-general. There's not much point in generalizing the monoid instance of the map as long as there is still an implicit Maybe in the values.
Actually at the moment lookup is.. lookup :: (Monad m,Ord k) => k -> Map k a -> m a Maybe we should have something like. lookupMaybe :: Ord k => k -> Map k a -> Maybe a lookupMonad :: (Monad m,Ord k) => k -> Map k a -> m a lookupMonoid :: (Ord k, Monoid a) => k -> Map k a -> a Hmm..
I'm not really advocating changing the Data.Map interface: Data.Map is intentionally specialized and optimized for pragmatic purposes. Abstract algebraic generalizations belong to Edison.
Or Jean-Philippes collections classes Regards -- Adrian Hey