Why is Maybe's Semigroup instance biased towards Just and the Monoid uses Nothing as its empty element?

Question

Maybe expresses computations that might not produce a result due to an error. Therefore such computations must be short circuited.

Now Maybe's Semigroup/Monoid instances seem to break with this semantics, because the former is biased towards Just and the latter treats the error case Nothing as its empty element:

Just "foo" <> Nothing -- Just "foo"
Nothing <> Just "bar" -- Just "bar"
Just "foo" <> Just "bar" -- Just "foobar"
Nothing <> Nothing -- Nothing

I would expect Nothing for the first two cases.

Here is the alternative implementation (hopefully it is correct/lawful):

instance Semigroup a => Semigroup (Maybe a) where
    Nothing <> _       = Nothing
    _       <> Nothing = Nothing
    Just a  <> Just b  = Just (a <> b)

instance Monoid a => Monoid (Maybe a) where
  mempty = Just mempty

I don't want to say that these alternative instances are better. But they seem useful too. So why was a selection made in the first place instead of leaving the implementation to the user?

Well that is one of the constraints a monoid has to satisfy: there is an empty element `0`, and `0 + x = x + 0 = x`. — Willem Van Onsem, May 04 '18 at 08:37
@WillemVanOnsem, yes, and OP's does satisfy that. Note: mempty = *Just* mempty. — luqui, May 04 '18 at 08:50
@luqui: but then that would mean that we have a `mempty` for `a` right? — Willem Van Onsem, May 04 '18 at 08:51
@WillemVanOnsem, we do, because of the `Monoid a =>` constraint. — luqui, May 04 '18 at 08:51
https://ghc.haskell.org/trac/ghc/ticket/1189#comment:1 link to the mailing list discussion, with its summary — max630, May 04 '18 at 09:02
You make the assumption that there is an "error" or "failure" semantic in the maybe, versus just a Nothing , Something semantic. The Nothing<>Something semantic is, is somehow equivalent to a list with 0 or 1 element. In that case, it seams natural that the concept of "empty" correspond to Nothing. For a list, you wouldn't expect `mempty` to be `[mempty]` wouldn't you ? — mb14, May 04 '18 at 11:08
@mb14 Sure, you can reduce the semantics of a type to its bare minimum. But `List` is a Monoid in its own right, whereas `Maybe` imposes a constraint on `a` (either `Semigroup a` or `Monoid a` depending on the implementation). So in case of `Maybe` we have to pick one. — , May 04 '18 at 12:37
Related: [Monoids for Maybe](https://byorgey.wordpress.com/2011/04/18/monoids-for-maybe/); [Option](https://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Semigroup.html#t:Option). — Daniel Wagner, May 04 '18 at 21:26

score 8 · Answer 1 · answered May 04 '18 at 09:05

Your instance is actually a special case of a much more general instance for applicative functors.

newtype LiftA f a = LiftA { getLiftA :: f a }

instance (Applicative f, Semigroup a) => Semigroup (LiftA f a) where
    LiftA x <> LiftA y = LiftA $ liftA2 (<>) x y

instance (Applicative f, Monoid a) => Monoid (LiftA f a) where
    mempty = LiftA $ pure mempty

Which I assumed would be in the standard library somewhere (under a different name probably) but I couldn't find it. But the existence of this general instance could be one reason to choose the library version of Maybe, which is more of Maybe's special power. On the other hand, it's quite nice when your algebraic structures are all coherent with each other; i.e. when a type is an Applicative, use the "LiftA"-style instance whenever possible (on all F-algebra classes).

On the third hand (!), we can't have coherence everywhere, since the library instance agrees with Maybe's MonadPlus instance. This is strikingly parallel to the fact that there are two monoids on natural numbers: addition and multiplication. For numbers, we just picked not to have any monoid instance because it's unclear which to use.

In conclusion, I don't know. But maybe this information was helpful.

So decision/compromises have to be made in Haskell, just like in imperative languages. But the possibility to decide is limited to the cases that the underlying mathematical framework allows, which is a big win - probably. — , May 04 '18 at 09:43
I see this issue coming from the core idea of typeclasses which is a sort of pun, pretending that types and algebraic structures are in perfect correspondence (e.g. there is only one way a type can be a monad). It's often, but not always true. But making that little lie makes a *lot* of things very convenient and cuts down on a lot of mess that would otherwise be there, manually keeping track of which algebraic structure we're talking about. But then there are cases like this where we have to pick favorites and/or disambiguate manually, and it can be cumbersome. — luqui, May 04 '18 at 09:50
Your answer along with the comment provides a great explanation for a vague question. Thank you! — , May 04 '18 at 10:03
["on the gripping hand"](http://www.catb.org/jargon/html/O/on-the-gripping-hand.html), perhaps? :) — rampion, May 04 '18 at 12:54

score 3 · Answer 2 · edited May 04 '18 at 17:55

I think the idea behind this is that Maybe is supposed to have the semantics that are actually only properly expressed by Option: it takes any semigroup and makes a monoid out of it, by adding Nothing as an ad-hoc “free mempty”. I.e. actually the instances should be

instance Semigroup a => Semigroup (Maybe a) where
  Nothing <> a = a
  a <> Nothing = a
  Just x <> Just y = Just $ x <> y

instance Semigroup a => Monoid (Maybe a) where
  mappend = (<>)
  mempty = Nothing

This is analogous to how [] gives the free monoid over any type, by adding both mempty and <>.

Of course, this requires that the Semigroup class is in base, which it wasn't until recently.

Corollary to this is that mempty becomes clearly pattern-matchable, because by parametricity it cannot depend on the contained type.

Practically speaking, this instance is arguably more useful then the one you propose, because as Luke remarked that is already covered by the Applicative instance so you can easily write liftA2 (<>) and pure mempty. Granted, the standard instance is also already covered by the Alternative instance, but Alternative/MonadPlus have always been considered as a bit hackish, inferior to the more mathematically impeccable Semigroup, Monoid, Functor and Applicative.

Why is Maybe's Semigroup instance biased towards Just and the Monoid uses Nothing as its empty element?

2 Answers2