haskellのMonoidのまとめ

Monoid Ordering
Monoid ()
Monoid Any
Monoid All
Monoid a => Monoid (Maybe a)
Monoid (Last a)
Monoid (First a)
Num a => Monoid (Product a)
Num a => Monoid (Sum a)
Monoid (Endo a)
Monoid a => Monoid (Dual a)
Monoid b => Monoid (a -> b)
(Monoid a, Monoid b) => Monoid (a, b)
(Monoid a, Monoid b, Monoid c) => Monoid (a, b, c)

instance MonadPlus []


## モノイド(monoid)とは

• 台集合 $M$
• 二項演算 $\cdot : M \times M \to M$
• 結合律を満たす
• 単位元 $e$

の組$(M,\cdot,e)$のこと。つまり

$\begin{array} \forall x, y, z \in M. x \cdot (y \cdot z) = (x \cdot y) \cdot z \\ \exists e \in M \mbox{ such that } \forall x \in M. e \cdot x = x \cdot e = x \end{array}$

class Monoid a where
mappend :: a -> a -> a
mempty  :: a


と定義され、

x mappend (y mappend z) = (x mappend y) mappend z
mempty mappend x = x mappend mempty = x


を満たすことが期待される。

(<>) :: Monoid a => a -> a -> a
(<>) = mappend
mconcat :: Monoid a => [a] -> a
mconcat = foldr mappend mempty


という便利な関数も定義されている。

## Sum, Product

haskellのNum*+を持っており環(ring)なので、どちらを使うのかnewtypeで包んで明示する必要がある。

>>> getSum (Sum 3 <> Sum 4)
7
>>> getProduct (Product 3 <> Product 4)
12
>>> getSum mempty
0
>>> getProduct mempty
1


## All, Any

Bool&&||を持っており環なので、Sum, Product同様wrapperが必要。

## Ordering

instance Monoid Ordering where
EQ mappend y = y
x  mappend y = x
mempty = EQ

>>> mconcat [EQ, EQ, EQ, GT, EQ, LT]
GT
>>> zipWith compare "aabc" "abcd"
[EQ,LT,LT,LT]
>>> let f x y = mconcat (zipWith compare x y) <> (compare on length) x y in f "aabc" "abcd"
LT


まあまあ便利。

## Endo

newtype Endo a = Endo (a -> a)


mappend ~ (.)
mempty  ~ id

>>> (appEndo . mconcat . map Endo) [(+ 1), (* 4), (+ 3)] 0
13


## Dual

>>> "foo" <> "bar"
"foobar"
>>> Dual "foo" <> Dual "bar"
Dual "barfoo"


## ()

>>> () <> ()
()
>>> mempty :: ()
()


## (,), (,,)

instance (Monoid a, Monoid b) => Monoid (a, b)


モノイドとモノイドの直積もモノイドになる。

>>> (Sum 3, Product 3) <> (Sum 4, Product 4)
(Sum 7, Product 12)


## x -> a

instance Monoid a => Monoid (x -> a)


## First, Last

$\begin{array} \forall a \in S. a \cdot e = e \cdot a = a \\ \forall a \in S \setminus \{e\}, b \in S. a \cdot b = a \end{array}$

とするとモノイド$(S,\cdot,e)$をなす。単位元でない最も左の要素が結果となるので左自明モノイドと呼ばれる。同様に右自明モノイドも考えられる。

haskellでは一般のデータに定義するためMaybeに包み単位元としてNothingを使う。Firstが左自明モノイド、Lastが右自明モノイドとしてinstance宣言されている。

>>> First (Just 'A') <> First (Just 'B')
First (Just 'A')
>>> (getLast . mconcat . map Last) [Just 'A', Nothing, Just 'B', Nothing, Nothing]
Just 'B'


## [a]

instance Monoid [a]


(<>) = (++)
mempty = []


## Maybe a

のだけど、haskellの標準にはSemigroupがないのでMonoidで代用している。memptyが定義されていないMonoidMaybeに突っ込むとちゃんとしたMonoidがでてくる。邪悪。

instance Monoid a => Monoid (Maybe a)


class Monad m => MonadPlus m where
mplus :: m a -> m a -> m a
mzero :: m a


Monadかつ引数与えるとMonoid。モノイドと同様、結合律と単位元を要求する。

instance MonadPlus []

であり、[]は自由モノイド、Maybeは左自明モノイドを生成する。