Monoid 型クラスについて勉強したことの整理

学習の素材は、
[すごいHaskellたのしく学ぼう!](http://www.amazon.co.jp/すごいHaskellたのしく学ぼう-Miran-Lipovača/dp/4274068854)

> この表記は、私見・感想です。

# Monoid
**モノイドのインスタンスである** とは、値を二項演算子で結合できるような型を指す。

```hs
class Monoid a where
        mempty  :: a
        -- ^ Identity of 'mappend'
        mappend :: a -> a -> a
        -- ^ An associative operation
        mconcat :: [a] -> a

        -- ^ Fold a list using the monoid.
        -- For most types, the default definition for 'mconcat' will be
        -- used, but the function is included in the class definition so
        -- that an optimized version can be provided for specific types.

        mconcat = foldr mappend mempty
```

## モノイド 則
モノイド型クラスのインスタンスは、次のモノイド則を守らなければならない。

```hs
mappend mempty x = x
mappend x mempty = x
mappend x (mappend y z) = mappend (mappend x y) z
mconcat = foldr mappend mempty
```

> Haskell が自動的に満たしてくれるルールではなく、プログラマが注意しなくてはならない。このルールを満たしていなくとも、表面上はモノイドのインスタンスとして宣言できるが、利用するとバグの温床となってしまう。


## Monoid インスタンス
[Monoid のインスタンス](http://hackage.haskell.org/package/base-4.7.0.2/docs/src/Data-Monoid.html#Monoid)には次のようなものがある。

* リスト
* Sum
* Product
* Any
* All
* Ordering
* Monoid a => Maybe a
* First a
* Last a

### `Maybe` モノイド
例えば、`Maybe` モノイドは、モノイドな型変数を持つ多相型となっている。

```hs:Maybe
instance Monoid a => Monoid (Maybe a) where
  mempty = Nothing
  Nothing `mappend` m = m
  m `mappend` Nothing = m
  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)
```

単位元( `mempty` ) は `Nothing` であり、`mappend` の左辺または右辺が `Nothing` の場合は、もう片方の値を採用する。両辺共に `Just`値であるなら、それぞれの内部的な値( これもモノイドのインスタンス) 同士を `mappend` する。

> 失敗するかもしれない計算の値がモノイドのインスタンスであることがわかっているなら、扱う値が`Just` か `Nothing` かを気にすることなく `mappend` することができる（パターンマッチして場合分けする必要がなくなる）。

なお、中身がモノイドかどうか不明な場合は、`First` モノイドや `Last` モノイドを使うことになる。

### `Ordering` モノイド
次に、`Ordering` モノイドを見てみる。

```hs
instance Monoid Ordering where
        mempty         = EQ
        LT `mappend` _ = LT
        EQ `mappend` y = y
        GT `mappend` _ = GT
```

単位元は`EQ` である。また`mappend` の実装は、左辺が`LT` または `GT` の場合は無条件でそれを返す。左辺が`EQ` の場合は、無条件で右辺を返す。このルールは、辞書式順序( lexicographic order ) と呼ばれている。

> 最初の比較結果で大小がわかればそれを採用し、等しければ次の比較結果を採用する。"book" と "body" とを比較すると一文字目は 'b' で`EQ` だが、二文字の'o'と'd'とを比較した結果、`GT` が返る、といったルールのこと。

また、次のように、比較条件を `mappend` することができる。

```
(\x y -> (length x `compare` length y) `mappend` (x `compare` y))
```

`Ordering` モノイドを利用すると、優先度の高い比較条件を一番左に持ってきて、以降優先度に従って右辺方向に比較条件を`mappend` することで複合的な比較条件を扱うことができるようになる。

> 上のラムダ式では、まず要素数で比較し、その次に辞書式順序で比較を行う操作を行っている。

## モノイドを活用して畳み込む
リストだけではなく、いろんなデータ構造を畳み込むことができる。それは、`Fodable` 型クラスのインスタンスにすること。一番簡単な方法として、、インタフェースとなる`foldMap` を実装すれば良い。

```hs
F.foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

class Foldable (t :: * -> *) where
  foldMap :: Monoid m => (a -> m) -> t a -> m
```


### あるデータ構造を`Foldable` にしてみる
自作ツリー構造のデータ型を、`Foldable` インスタンスにしてみる。

```hs
data Tree a =   EmptyTree
            |   Node a (Tree a) (Tree a)
            deriving (Show)

instance F.Foldable Tree where
    foldMap f EmptyTree = mempty
    foldMap f (Node x l r) = F.foldMap f l `mappend` f x  `mappend` (F.foldMap f r)

-- ちなみにFunctor のインスタンスにするにはこのような形
instance Functor Tree where
    fmap f EmptyTree = EmptyTree
    fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)
```

> この時点では、ある値をモノイド値に変換する関数を定義する必要がない。
> foldMap では、引数に与えられる関数をどのように適用して`mappend` させるか、という点を定義する。

これで、データ型`Tree` に対して `foldr` が使えるようになった。
なお `foldMap` も、単体で使用できる関数である。例えば次のように、任意のデータ構造をリスト( モノイド )に変換することができる。

```hs
Data.Monoid F> F.foldMap (\x -> [x]) $ Node 3 (Node 1 EmptyTree EmptyTree) (Node 100 EmptyTree EmptyTree)
-- [1,3,100] が返る
```