mempty with different definition depending on whether mempty is left or right arg?

Question

I have the following datatype and semigroup instance:

data Or a b =
  Fst a
  | Snd b deriving (Eq, Show)

instance Semigroup (Or a b) where
  (<>) (Fst a) (Fst b) = Fst b
  (<>) (Snd a) (Fst b) = Snd a
  (<>) (Fst a) (Snd b) = Snd b
  (<>) (Snd a) (Snd b) = Snd a

I want to make a monoid instance for the type above, but I do not see how to do it. If I use the following definition

instance (Monoid a, Monoid b) => Monoid (Or a b) where
  mempty = (Fst mempty)
  mappend = (<>)

it will work on all pairs of input to <>, except the one where I mappend

(Fst a) <> mempty

which will evaluate to mempty.

How do I fix this so that the mempty is valid? It seems like it cannot be done without some new syntax or concepts since it hinges on whether the mempty is to the left or right...

It doesn't seem like you actually have a monoid here, to be honest. There isn't an identity element. — Louis Wasserman
Strange. Implementing a monoid for it is an exercise from the Haskell book, haskellbook.com — The Unfun Cat

Daniel Wagner Daniel Wagner · Accepted Answer · 2016-03-08T20:44:39

There is a perfectly good (and simpler) semigroup which always takes its first argument:

newtype FirstS a = FirstS a
instance Semigroup (FirstS a) where
    a <> b = a

Unfortunately, it is not a monoid because -- except for trivial choices of wrapped type -- there is no left identity of this operation. The standard First type patches FirstS by adding a distinguished identity element, thus:

newtype First a = First (Maybe a)
instance Semigroup (First a) where
    First Nothing <> b = b
    a <> First Nothing = a
    a <> b = a -- this clause is exactly as before

Then it is easy to write the Monoid instance by choosing mempty = First Nothing. You can pull a similar trick by adding a distinguished identity element to your type:

data Or a b = Fst a | Snd b | Neither
instance Semigroup (Or a b) where
    Neither <> b = b
    a <> Neither = a
    -- the remainder of the clauses are as before

This makes the choice of mempty = Neither quite easy.

This pattern is so frequently useful that it actually has a newtype wrapper in semigroups, so that you could also write this patched type using your original Or a b type as simply Option (Or a b) and get the Semigroup and Monoid instances for free.

mempty with different definition depending on whether mempty is left or right arg?

1 Answers