[Haskell-cafe] commutative monoid?

[wren ng thornton]

On 6/25/11 1:34 AM, Evan Laforge wrote:
> So there's a range of possible Monoid instances for each type,

More for some types than for others. For Maybe there are three:

 * always take the first/left value;
 * always take the last/right value;
 * or, use a semigroup operation defined on the values.

The first two options are provided by the First and Last newtypes, and the
third option is provided by the instance for Maybe itself (except that it
spuriously requires a Monoid instance instead of just a semigroup).

For integers there are at least four obvious ones (min, max, addition,
multiplication), and numerous less obvious ones. For real numbers we can
also add the logarithmic and exponential versions. Etc.


> maybe they were chosen by historical happenstance rather than some
> kind of "principle monoid" (is there such a thing?).  Is there a name
> for the thing that's like a monoid, but the operator is commutative
> too?

"Commutative monoid" :)

> That would narrow down the implementation choices, e.g. Data.Map
> would have to combine the values.  So it seems like if your operation
> is commutative, you can put it in "c-monoid" and not rely so much on
> the happenstance of the instances, since they are more constrained.

They're more constrained, but still not enough to make things unique. All
four of the obvious ones I mentioned for integers are commutative.

You could keep constraining things further. But how constrained do you
want to be? In some sense, there will always be room for multiple
interpretations. Occasionally things magic their way into being unique,
but usually not. Much of the last century of physics has been spent
debating between different interpretations of some extremely constrained
systems. So far as I'm aware, there's still no consensus about which
interpretation is "right".

> And of course you are then free to reorder things, which is a nice bit
> of flexibility.

Indeed, commutativity is a wonderful property to take advantage of when
you can.

> So is there a typeclass for that?

There might be one hidden in one of the attempts at redesigning the
numeric hierarchy (e.g., Numeric Prelude), but there's not a canonical
typeclass for them. Unfortunately it's not really a good match for the
typeclass system since it doesn't introduce any new operations, it only
introduces laws--- which aren't verified nor enforced.

Though, if you happen to know the property does hold, then you're free to
take advantage of it. (E.g., for the Maybe instance which uses a semigroup
operation, if the semigroup op is commutative then so is the monoid op.)

-- 
Live well,
~wren