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?

Waldgrave

Well that is one of the constraints a monoid has to satisfy: there is an empty element 0, and 0 + x = x + 0 = x. – Vevina

@WillemVanOnsem, yes, and OP's does satisfy that. Note: mempty = Just mempty. – Manikin

@luqui: but then that would mean that we have a mempty for a right? – Vevina

@WillemVanOnsem, we do, because of the Monoid a => constraint. – Manikin

Aargh... Yes, I overlooked the Monoid a constraint :( – Vevina

ghc.haskell.org/trac/ghc/ticket/1189#comment:1 link to the mailing list discussion, with its summary – Infelicitous

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 ? – Propend

@Propend 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. – Waldgrave

Related: Monoids for Maybe; Option. – Salop

Answer 1

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.

Manikin

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. – Waldgrave

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. – Manikin

Your answer along with the comment provides a great explanation for a vague question. Thank you! – Waldgrave

"on the gripping hand", perhaps? :) – Brandwein

Answer 2

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.

Hanfurd