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 []
instance MonadPlus Maybe

モノイド(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}\]

haskellでは

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

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

単位元を除くと半群(semigroup)、逆元の存在を加えると群(group)になる。

(<>) :: 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

任意のモノイド$(M,\cdot,e)$に対しその二項演算$\cdot$の引数の順を逆にした二項演算$b \star a := a \cdot b$を考えると、$(M,\star,e)$もまたモノイド。

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

()

任意の単元集合${e}$は$e \cdot e = e$とするとモノイド。自明なモノイドと呼ばれる。

>>> () <> ()
()
>>> 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)

任意の集合からモノイドへの関数はモノイド。$f \star g := \lambda x. f(x) \cdot g(x)$とする。単位元は$\lambda x. e$。

上の積の例の一般化と言える。hom集合には値域の性質が入る。

First, Last

任意の集合$S$に対し、そのある特別な要素$e \in S$を定めると、

\[\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 = []

要素が何であれモノイドの公理を満たし、かつ余分な等式を作らないので、自由モノイドと呼ばれる。例えば点を加えて左自明モノイドを作ると$\forall a \in S \setminus {e}. \forall b, c \in S. a \cdot b = a \cdot c$のような等式ができるが、そういうものがないということ。

Maybe a

任意の半群に単位元として一点足せばモノイドになる。

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

instance Monoid a => Monoid (Maybe a)

MonadPlus

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

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

instance MonadPlus []
instance MonadPlus Maybe

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

Data.Monoidを眺めた

参考

モノイドからモナドが作れるだとか、左/右自明モノイドと単一代入/破壊的代入が関連するとか聞いたりして、今一度見てみたら面白かったので書いた。

記述時のbaseは4.7.0.1でした