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 may be turned into a monoid simply by adjoining an element not in and defining and for all ." Since there is no Semigroup type class providing just mappend, we use Monoid instead.

  (Actually, there is (now) a Semigroup type class…)

  *Main> 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?

Call for contributions: second edition of the Typeclassopedia

The Typeclassopedia, by all accounts, has turned out to be a popular and useful resource for Haskell programmers. I’ve been thinking for a while about putting out a revised and expanded second edition, and it’s finally time. Planned changes include:

• making suggested exercises stand out typographically and adding many more;
• updating information about various standard packages (mtl, transformers, etc.) to match the current state of affairs;
• switching away from Pointed as a stepping stone to Applicative in favor of a more semigroupoid-based approach;
• expanding the sections on comonads and arrows, which were a bit rushed in the first edition;
• many other small additions, clarifications, and corrections.

However, the first edition was immeasurably improved by suggestions and contributions from many readers, and I hope the same will be true for the second. So, what would you like to see in the second edition? Some prompts to help you think of ways to contribute:

• Is there a section you find confusing? Do you have a suggestion to improve its clarity?
• Do you have a suggestion for a good exercise?
• Do you know of an error, whether technical or typographical?
• Do you know of a good resource that could be added to the bibliography — an explanation, example, original/historical source, relevant humor, … ?
• Are you able and willing to contribute some text explaining some aspect of a more advanced type class (Category, Comonad, Arrow, …) in more depth, or more intuitively, than the existing text?

To contribute, you can send me email (byorgey at cis dot upenn dot edu). I’ll also be keeping this darcs repository up to date, so you’re welcome to send me darcs patches as well.