Why isn't Data.Map not an instance of Monoid :-)

[Lauri Alanko]

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

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.

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.


Lauri