Monoids for Maybe

The other day I had two lists of monoidal values that I wanted to combine in a certain way, and I realized it was an instance of this more general pattern:

> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
> import Data.Monoid
> import Control.Applicative
> 
> (<>) :: Monoid m => m -> m -> m
> (<>) = mappend   -- I can't stand writing `mappend`
> 
> newtype AM f m = AM { unAM :: f m }
>   deriving (Functor, Applicative, Show)
> 
> instance (Applicative f, Monoid m) => Monoid (AM f m) where
>   mempty        = pure mempty
>   mappend f1 f2 = mappend <$> f1 <*> f2

It’s not too hard (although a bit fiddly) to show that AM f m satisfies the monoid laws, given that f and m satisfy the applicative functor and monoid laws respectively.

The basic idea here is that the mappend operation for AM f m is just the mappend operation for m, but applied "idiomatically" in the f context. For example, when f = [], this combines two lists of monoidal values by combining all possible pairs:

*Main> map getProduct . unAM $ (AM (map Product [1,2,3]) 
                                <> AM (map Product [1,10,100]))
[1,10,100,2,20,200,3,30,300]

In the #haskell IRC channel someone pointed out to me that Data.Monoid has an instance Monoid m => Monoid (e -> m) which is just a special case of this pattern:

*Main> :m +Data.Ord
*Main Data.Ord> map ((unAM $ AM (comparing length) 
                             <> AM compare) "foo") 
                    ["ba", "bar", "barr"]
[GT,GT,LT]
*Main Data.Ord> map ((comparing length <> compare) "foo") 
                    ["ba", "bar", "barr"]
[GT,GT,LT]

It was also mentioned that the monoid instance for Maybe is also a special case of this pattern:

*Main> AM (Just (Sum 3)) <> AM Nothing
AM {unAM = Nothing}
*Main> Just (Sum 3) <> Nothing
Just (Sum {getSum = 3})

Wait, hold on, what?! It turns out that the default Monoid instance for Maybe is not an instance of this pattern after all! I previously thought there were three different ways of declaring a Monoid instance for Maybe; I now know that there are (at least) four.

• The default instance defined in Data.Monoid uses Nothing as the identity element, so Nothing represents "no information". It requires a Monoid constraint on the type wrapped by Maybe, although Monoid is slightly too strong, since the type’s own identity element is effectively ignored. In fact, the Data.Monoid documentation states

  Lift a semigroup into Maybe forming a Monoid according to http://en.wikipedia.org/wiki/Monoid: "Any semigroup \(S\) may be turned into a monoid simply by adjoining an element \(e\) not in \(S\) and defining \(e*e = e\) and \(e*s = s = s*e\) for all \(s \in S\)." Since there is no Semigroup type class providing just mappend, we use Monoid instead.

  <p>(Actually, there is (now) <a href="http://hackage.haskell.org/packages/archive/semigroups/0.3.4.1/doc/html/Data-Semigroup.html#t:Semigroup">a <code>Semigroup</code> type class</a>...)</p><pre><code>*Main&gt; mconcat [Just (Sum 3), Nothing]

  Just (Sum {getSum = 3}) *Main> mconcat [Just (Sum 3), Nothing, Just (Sum 4), Nothing] Just (Sum {getSum = 7})

• The First newtype wrapper in Data.Monoid just takes the first non-Nothing occurrence:

  *Main> mconcat . map First $ [Nothing, Just 3, Nothing, Just 4]
  First {getFirst = Just 3}
  

  This is actually the same as the MonadPlus instance for Maybe, where mplus is used to choose the first non-failing computation:

  *Main Control.Monad> Nothing `mplus` 
                       Just 3 `mplus` 
                       Nothing `mplus` 
                       Just 4
  Just 3
  

• The Last newtype wrapper is the dual of First, taking the last non-Nothing occurrence:

  *Main> mconcat . map Last $ [Nothing, Just 3, Nothing, Just 4]
  Last {getLast = Just 4}
  

• The Monoid instance following the Applicative structure of Maybe, however, is distinct from all of these. It combines values wrapped by Just according to their own Monoid instance, but if any occurrences of Nothing are encountered, the result is also Nothing. That is, it corresponds to combining monoidal values in the presence of possible failure, that is, applying mappend idiomatically within the applicative context.

  *Main> mconcat [AM (Just (Sum 3)), AM (Just (Sum 4))]
  AM {unAM = Just (Sum {getSum = 7})}
  *Main> mconcat [AM (Just (Sum 3)), AM (Just (Sum 4)), AM Nothing]
  AM {unAM = Nothing}
  

  As far as I know, this instance is nowhere to be found in the standard libraries. Perhaps a wrapper like AM should be added to Control.Applicative?