[RFC] New MonoidMap type

[jonathanknowles]

@turion

One viewpoint for MonoidMap can also be that of a “weighted set”, where all keys with a value different from mempty are viewed as being an element of the set, and the value measures the “weight” of this membership. An example for this are discrete probability distributions. The monoid in question is simply the nonnegative reals with addition. You can recover ordinary sets by chosing the monoid Maybe (), where mempty is “no membership” and Just () is “membership”. So I find this quite useful.

Thanks for sharing this viewpoint! I also like the “weighted set” intuition.

By adjusting the monoidal value type, we can reproduce several similar types (and use newtype deriving to get instances of Semigroup, Monoid, and relevant subclasses):

newtype Map k v = Map (MonoidMap k (First  v))
newtype Set k   = Set (MonoidMap k (Maybe ()))

newtype       MultiSet k =       MultiSet (MonoidMap k (Sum Natural))
newtype SignedMultiSet k = SignedMultiSet (MonoidMap k (Sum Integer))

newtype     MultiMap k v =     MultiMap (MonoidMap k (Set v))
newtype ListMultiMap k v = ListMultiMap (MonoidMap k     [v])

[googleson78]

@hasufell

Exciting, but I have a hard time understanding boring real world use cases.

Regarding boring use cases, I’m 100% sure you’ve ran into the task of having to aggregate a bunch of values in some form (e.g. into a list, sum them, only take the first one, etc) based on their keys. This package would be extremely useful then, to reduce some of the “boilerplate” that usually arises there.