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
usesNothing
as the identity element, soNothing
represents "no information". It requires aMonoid
constraint on the type wrapped byMaybe
, althoughMonoid
is slightly too strong, since the type’s own identity element is effectively ignored. In fact, theData.Monoid
documentation states
Lift a semigroup into
Maybe
forming aMonoid
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 noSemigroup
type class providing justmappend
, we useMonoid
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 inData.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 forMaybe
, wheremplus
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 ofFirst
, taking the last non-Nothing
occurrence:*Main> mconcat . map Last $ [Nothing, Just 3, Nothing, Just 4] Last {getLast = Just 4}
-
The
Monoid
instance following theApplicative
structure ofMaybe
, however, is distinct from all of these. It combines values wrapped byJust
according to their ownMonoid
instance, but if any occurrences ofNothing
are encountered, the result is alsoNothing
. That is, it corresponds to combining monoidal values in the presence of possible failure, that is, applyingmappend
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 toControl.Applicative
?
What is mempty in the latter case?
AM (pure mempty).
I called that monoid ‘App’ in my ‘monoids’ package a couple of years back.
http://hackage.haskell.org/packages/archive/monoids/0.2.0.2/doc/html/Data-Monoid-Applicative.html
-Edward
Ah, nice, I should have known you already had this in some package somewhere. =)
@Long Huynh Huu
It’s `Just mempty’: Just x Just mempty = Just (x mempty) = Just x; Nothing Just mempty = Nothing. And similarly it’s a left identity.
In fact there are 6 Monoid instances (again at least) for Maybe a. Any instance which exploit monoidal structure of a could use dual monoid as well. This makes six instances without adding much of substance.
Also default instance of Maybe not use mempty and could be though as transformer of semigroup into monoid.
And we can replace Monoid with any equational algebraic theory. I.e., if
C0 C1:cartesian monoidal category
F:C0 monoidal→ C1
T:equational algebraic theory
then
F:Mod(T,C0)→Mod(T,C1)
my post
My comment is not quite correct. To make it correct, replace
T:equational algebraic theory
with
T:algebraic theory with monoidal equations
or replace
F:C0 monoidal→ C1
with
F:C0 preserving products→ C1