`Sem`

.data Sem a = ... -- doesn't matter

In the spirit of defining every typeclass instance you can think of—a spirit that I share, believe me—you discover a monoid, and suggest that it be included with

`Sem`

.instance ??? => Monoid (Sem a) where -- definition here

But then, you are surprised to encounter pessimism and waffling, from me!

I’m so skeptical of your monoid because it is “common”; many monoids simply fall out of numerous monads, to greater or lesser degree, but that doesn’t make them “good” monoids. Having rediscovered a common, uninteresting monoid, you need to provide more justification of why it should be “the” monoid for this data type.

## The lifted monoid

*Every*applicative functor gives rise to a monoid that lifts their arguments’ monoid.

instance Monoid a => Monoid (Sem a) where mempty = pure mempty mappend = liftA2 mappend

This is “the” monoid for

`(->) r`

and `Maybe`

. It is decidedly *not*the monoid for

`[]`

. For in that universe,> [Sum 2] `mappend` [Sum 3, Sum 7] [Sum 5, Sum 9] > [Sum 42] `mappend` [] []

Maybe you reaction is “but that’s not a legal monoid!” Sure it is. The

`mappend`

is based on combination, just as `Applicative []`

’s `<*>`

is. And, in the example above, the left and right identity is
`[Sum 0]`

, not `[]`

.It’s just not the monoid you’re used to.

Moreover, it isn’t quite right for

`Maybe`

! The constraint
generalizes to `Semigroup a`

. It is an unfortunate accident of
history that the constraint on Haskell `Maybe`

’s monoid is also
`Monoid`

.Even the choice for

`(->) r`

makes many people unhappy, though we’re
not quite ready to explore the reason for that.So, what makes you think this is a good choice for

`Sem`

? It’s not
enough justification that it can be written; that is always the case.
There must be something that makes `Sem`

like `(->) r`

or `Maybe`

, and
not like `[]`

.##
The `MonadPlus`

monoid

To be entirely modern, this would be the `Alternative`

monoid.
Despite the possibilities for equivocation, this monoid is just as
good as any other.Simply: every

`Alternative`

(a subclass of `Applicative`

and a
superclass of the more well-known `MonadPlus`

) gives rise to a monoid
that is *universal*over the argument, no

`Monoid`

constraint
required.-- supposing Alternative Sem, instance Monoid (Sem a) where mempty = empty mappend = (<|>)

You would not be surprised at this having prepared by reading the haddock for

`Alternative`

:
“a monoid on applicative functors”, it says.`[]`

is `Alternative`

, and indeed this is the monoid of choice for
`[]`

. But `Maybe`

is also `Alternative`

. Why is this one good for
`[]`

, but not `Maybe`

? Let’s take a peek through the looking glass.> Just 1 `mappend` Just 4 Just 1 > Nothing `mappend` Just 3 Just 3

I happen to agree with the monoid of choice for

`Maybe`

. But I’m sure
many have been surprised it’s not “just take the leftmost `Just`

, or
give `Nothing`

”.Except where phantom

`Const`

-style functors
are involved, the two preceding monoids always have incompatible
behavior. One sums the underlying values, the other never touchs
them, only rearranging them. So, if both are available to `Sem`

, to
define a monoid, we must give up at least one of these.Alternatively, we could put off the decision until someone comes up with a convincing argument for “the” monoid.

## The category endomorphism monoid

This monoid hasn’t let the lack of a pithy name handicap it; despite the stunning blow of losing the prized`(->)`

to the lifted monoid
(the commit),
this one probably has even more fans eager for a rematch today than it
did back then.I’m referring to this one, still thought of as “the” monoid for

`(->)`

by some.instance Monoid (a -> a) where mempty = id mappend = (.)

The elegance of this kind of “summing” of functions is undeniable. Moreover, it applies to

*every*

`Category`

, not just `(->)`

. Even
more, it works for anything sufficiently `Category`

-ish, such as
`ReaderT`

.instance Monad m => Monoid (ReaderT a m a) where mempty = ask ReaderT f `mappend` ReaderT g = ReaderT $ f <=< g

Its fatal flaw is that twin appearance of

`a`

; it requires
`FlexibleInstances`

, so can’t be written in portable Haskell 2010.
As such, it will probably remain in the minor leagues of newtypes like
`Endo`

.Moreover, should you discover it for

`Sem`

, its applicability to *any*category-ish thing should

*still*give you pause.

## The burden of proof

In Haskell, hacking until it compiles is a great way to work. It is tempting to rely on its conclusions in ever more cases, once you have discovered its effectiveness. However, in the cases above, it is very easy to be led astray by the facile promises of the typechecker.Introducing one of these monoids is risky. It precludes the later introduction of the “right” monoid for a datatype, for want of compatibility. If you really must offer one of these monoids as “the” monoid for a datatype, the responsibility falls to you: demonstrate that this is a

*good*monoid, not just an easy one.

## 1 comment:

The issue with the

instance Monoid (a -> a)

is that it has _terrible_ type inference. The FlexibleInstances requirement is the compiler telling you not just that "hey this isn't Haskell 98" but that it may not be able to help you without type annotations.

Simple code like `const 1 <> (+) 2` will fail to work with that instance. Why? Well, they are too polymorphic for the instance to resolve.

instance a ~ b => Monoid (a -> b)

would resolve that issue at least, but now drags you even _farther_ into exotic type extensions land.

Post a Comment