Haskell 型クラス覚書（Functor、Applicative、Monad、Semigroup、Monoid、MonadPlus、Alternative）

Haskell にあらかじめ備えられている型クラスは、それを知らなくても Haskell のプログラムを書き下すことは可能ですが、知っているとコンパクトに、再利用可能で、曖昧さのないようにプログラムを書き下すことができるようになります。実用的なライブラリの中核となるデータ型はほとんどの場合で `Monad` を含む複数の型クラスを実装しています。そのようなライブラリを使いこなすためには、型クラスの特性を知っておく必要があり、また自身で作成したデータ型に型クラスを実装するに際してもまた、型クラスの特性を知っておく必要があるわけです。

本記事では、Haskell のよく使う以下型クラスの覚書です。

- `Functor`
- `Applicative`
- `Monad`
- `Semigroup`
- `Monoid`
- `Alternative`
- `MonadPlus`

`Show`、`Eq`、`Ord` などももちろん Haskell の主要な型クラスではあるのですが、本記事では扱いません。

上述の型クラスの特性を把握するために上記すべてを実装する型を定義しながら型クラスを学ぶことにします。基本となる型は以下のパーサとします。

```hs
newtype Parser a = Parser {
  parse :: ReadS a
}
```

なお、`ReadS a` は `Prelude` で以下のように定義されている、`String` から `a` に変換するパーサのための型です。

```hs
type ReadS a = String -> [(a, String)]
```

`Parser a` とは `String` を受け取り `[(a, String)]` を返す関数を包む型です。関数を型で包んでいるのは、関数のままだと型クラスに適用できないためです。`[(a, String)]` の `a` はパースした結果の値、`String` はパース後に余った文字列です。`Prelude` の定義通り、パースに成功した場合は 1 要素のみ持つリスト、パースに失敗した場合は `[]` を返すものとします[^why-tuple-list]。

またパーサコンビネータとして、先頭 1 文字を取得する `item` という関数と、パース失敗を表す `failure` を以下のように定義します。

```hs
item :: Parser Char
item = Parser $ \s -> case s of
  [] -> []
  (c:cs) -> [(c, cs)]

failure :: Parser a
failure = Parser $ const []
```

このコンビネータは以下のように使用します。

```hs
> parse item "abc"
[('a',"bc")]
> parse item ""
[]
>
```

## Functor

`Functor` は包まれた対象に関数を適用するもの、と捉えておけば良いと思います。圏とか射とか難しい定義があるのですが、それらの難しい説明は今度の機会にします。

以下はリストと `Maybe` の `Functor` における振る舞いです。

```hs
> (+ 3) `fmap` [1, 2, 3]
[4,5,6]
> (+ 3) <$> [1, 2, 3]
[4,5,6]
> (+ 3) <$> []
[]
> (+ 3) <$> Just 1
Just 4
> (+ 3) <$> Nothing
Nothing
>
```

`<$>` は `fmap` の同義語です。訓練されると `<$>` の方が読みやすくなります。

`Parser a` を `Functor` のインスタンスにするには以下のように定義します。

```hs
instance Functor Parser where
  f `fmap` (Parser p) = Parser $ \s -> [(f x, s1) | (x, s1) <- p s]
```

`Parser $ \s -> [(f x, s1) | (x, s1) <- p s]` が一見分かりづらいですが、`Parser a` が関数を包む型というのを思い出せば、`\s -> [(f x, s1) | (x, s1) <- p s]` が `s` を引数に取り、`p` に適用した結果の値の方に `f` を適用する、ということが見て取れます。

`Parser a` を `Functor` のインスタンスにすると、以下のように書き下すことができます。

```hs
> :m + Data.Char
> parse (toUpper <$> item) "abc"
[('A',"bc")]
> parse (toUpper <$> failure) "abc"
[]
> parse (toUpper <$> item) ""
[]
>
```

`function <$> Functor` というイディオムを覚えてしまうと良いでしょう。

## Applicative

`Functor` が関数に包まれた値を適用するのに対し、`Applicative` は包まれた関数に包まれた値を適用します。というよりむしろ、順番にまとめて関数に包まれた値を適用する、という方がイメージが近いです。

以下はリストの `Applicative` における振る舞いです。

```hs
> pure (,,) <*> [1, 2] <*> [3, 4] <*> [5, 6]
[(1,3,5),(1,3,6),(1,4,5),(1,4,6),(2,3,5),(2,3,6),(2,4,5),(2,4,6)]
> (,,) <$> [1, 2] <*> [3, 4] <*> [5, 6]
[(1,3,5),(1,3,6),(1,4,5),(1,4,6),(2,3,5),(2,3,6),(2,4,5),(2,4,6)]
> (,,) <$> [1, 2] <*> [3, 4] <*> []
[]
>
```

`pure (,,) <*>` と `(,,) <$>` は同義ですが、`Applicative` は `Functor` のサブクラスで `<$>` が使用できることが保証されるため、後者のほうが冗長さがなく好まれます。`<*>` はいくつでも連結することができるのですが、先頭の関数が取る引数と同じでなければなりません。

`Parser a` を `Applicative` のインスタンスにするには以下のように定義します。

```hs
instance Applicative Parser where
  pure x = Parser $ \s -> [(x, s)]
  (Parser p1) <*> (Parser p2) =
    Parser $ \s -> [(f x, s2) | (f, s1) <- p1 s, (x, s2) <- p2 s1]
```

`<*>` は、`p1` という関数を返す関数と `p2` という値を返す関数があり、そこに文字列 `s` が渡された場合に、まず `s` を `p1` に適用した結果の余剰文字列 `s1` を `p2` に適用し、得られた `x` を `p1` が返した関数 `f` に適用したものと、`p2` の余剰文字列 `s2` を返す関数を定義しています。

`pure` は見たとおりです。渡された値 `x` はそのままなのはもちろん、文字列 `s` を次の `Applicative` のためにそのまま残すのがポイントです。

`Parser a` を `Applicative` のインスタンスにすると、以下のように書き下すことができます。

```hs
> parse ((,,) <$> item <*> item <*> item) "abcdef"
[(('a','b','c'),"def")]
> parse ((,,) <$> item <*> item <*> item) ""
[]
> parse ((,,) <$> item <*> item <*> failure) "abcdef"
[]
>
```

`Parser a` が後述する `Monad` を実装していれば、以下のように書き換えられます。

```hs
> :{
| tuple :: Parser (Char, Char, Char)
| tuple = do
|   x <- item
|   y <- item
|   z <- item
|   return (x, y, z)
| :}
> parse tuple "abcdef"
[(('a','b','c'),"def")]
>
```

`do` 記法は処理の順序がわかりやすいですね。ただし、この書き方よりも前述の `<$>`、`<*>` を用いた書き方を推奨します[^applicative-style-recommendations]。

さて、このように `Applicative` は `Functor` の `<$>` と組み合わせることで威力を発揮することがわかりました。例えば最初の 3 文字を大文字にするパーサは以下のように書き下します。

```hs
> :m + Data.Char
> parse ((\x y z -> map toUpper [x, y, z]) <$> item <*> item <*> item) "abcdef"
[("ABC","def")]
>
```

本記事ではコンビネータを `item` と `failure` に限定しているので大したことはできませんが、コンビネータを充実させることで複雑な文字列が簡単にパースできそうな気がしてきませんか。

## Monad

`Applicative` が包まれた値をまとめて順番に関数に適用するのに対し `Monad` は包まれた値を、ひとつずつ順番に関数に適用します。

日本語だとすごく分かりづらいのですが、以下の例を見ればわかりやすいと思います。

```hs
> let decuple x = [x * 10]
> [1, 2, 3] >>= decuple
[10,20,30]
> [1, 2, 3] >>= decuple >>= decuple
[100,200,300]
```

`Applicative` が `関数 <$> 値 <*> 値 <*> 値` だったのに対し、`Monad` は `値 >>= 関数 >>= 関数 >>= 関数` です。値を連続させるか関数を連続させるかの違いです。パーサで言えば、`Applicative` は文字列を次々に消化していくのに対し、`Monad` はパースした値を次々と変えていく、というイメージです。`Monad` で適用する関数は `\x -> [x * 10]` のように `Monad` ではない値を受け取り `Monad` で包まれた値に変換する必要があり、この関数こそがパーサにおけるコンビネータです。今回のパーサであれば `\x -> Parser $ \s -> [(toUpper x, s)]` という感じになります。

`Parser a` を `Monad` のインスタンスにするには以下のように定義します。

```hs
instance Monad Parser where
  (Parser p) >>= f = Parser $ \s -> (\(x, s') -> parse (f x) s') `concatMap` p s
  return = pure
```

`Parser a` を `Monad` のインスタンスにすると、以下のように書き下すことができます。

```hs
> :m + Data.Char
> let toUpperM x = Parser $ \s -> [(toUpper x, s)]
> let toStringM x = Parser $ \s -> [([x], s)]
> parse (item >>= toUpperM >>= toStringM) "abc"
[("A","bc")]
> parse (item >>= toUpperM >>= toStringM) ""
[]
>
```

`Monad` については以下のモナド則という規則を満たしていなければなりません。

```hs
return x >>= f = f x
m >>= return = m
(m >>= f) >>= g = m >>= (\x -> f x >>= g)
```

ここでは省略しますが今回の `Parser a` はモナド則を満たしています。

## Semigroup

`Semigroup` とは対象となる包まれたふたつの値を結合してひとつにするものです。結合の方法はその対象の値ごとにルールが異なりますが、以下を見ればわかると思います。

```hs
> [1, 2] <> [3, 4] <> [5, 6]
[1,2,3,4,5,6]
> Sum 1 <> Sum 2 <> Sum 3
Sum {getSum = 6}
>
```

`[a]` では `++`、`Sum` では `+` で `<>` が実装されているのではないかと予測できます。

`Parser a` を `Semigroup` のインスタンスにするには以下のように定義します。

```hs
instance Semigroup (Parser a) where
  (Parser p1) <> (Parser p2) = Parser $ \s -> case p1 s of
    [] -> p2 s
    r -> r
```

パース結果（`[(a, String)]` の `a`）は結合できるかどうかも、その結合方法も自明ではないため、`Parser a` の `<>` は左辺が有効なら左辺、そうでないなら右辺という選択式とします。

`Parser a` を `Semigroup` のインスタンスにすると、以下のように書き下すことができます。

```hs
> parse (return 'A' <> item) "abc"
[('A',"abc")]
> parse (Parser (const []) <> item) "abc"
[('a',"bc")]
>
```

`Semigroup` には `Monad` におけるモナド則であるセミグループ則を満たしていなければなりません。

```hs
x <> (y <> z) == (x <> y) <> z
```

ここでは省略しますが今回の `Parser a` はセミグループ則を満たしています。

## Monoid

`Monoid` は `Semigroup` のサブクラスで、`Semigroup` の対象ふたつを結合できる性質に加え、単位元を導出する関数を提供する必要があります。

リストの例としては以下の通りです。

```hs
> mempty :: [Int]
[]
> [1, 2, 3] `mappend` [4, 5, 6]
[1,2,3,4,5,6]
>
```

`Parser a` を `Monoid` のインスタンスにするには以下のように定義します。

```hs
instance Monoid (Parser a) where
  mempty = Parser $ const []
  mappend = (<>)
```

`Parser a` を `Monoid` のインスタンスにすると、以下のように書き下すことができます。

```hs
> parse (mempty <> mempty <> item) "abc"
[('a',"bc")]
> parse (mempty <> mempty <> item) ""
[]
>
```

`Monoid` には `Monad` におけるモナド則であるモノイド則を満たしていなければなりません。

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

ここでは省略しますが今回の `Parser a` はモノイド則を満たしています。

## Alternative

`Alternative` は可能性を表す型です。可能性には失敗と成功があり、`Alternative` では失敗を表す値を返す `empty` と、失敗、成功を含む可能性の結合を行う `<|>` を定義する必要があります。その他にひとつ以上を表す `some`、ゼロ以上を表す `many` が利用できます[^please-tell-me-how-to-use-some-and-many]。

リストと `Maybe` の例としては以下の通りです。

```hs
> empty :: [Int]
[]
> [1, 2, 3] <|> [4, 5, 6]
[1,2,3,4,5,6]
> empty :: Maybe Int
Nothing
> Just 1 <|> Nothing
Just 1
> Nothing <|> Just 2
Just 2
> Just 1 <|> Just 2
Just 1
> Nothing <|> Nothing
Nothing
```

`Parser a` を `Alternative` のインスタンスにするには以下のように定義します。

```hs
instance Alternative Parser where
  empty = mempty
  (<|>) = (<>)
```

`Parser a` を `Alternative` のインスタンスにすると、以下のように書き下すことができます。

```hs
> :m + Control.Applicative
> parse (empty <|> empty <|> item) "abc"
[('a',"bc")]
> parse (empty <|> empty <|> item) ""
[]
>
```

ここでの使い方は `Monoid` と変わりません。

## MonadPlus

`MonadPlus` は `Alternative` と `Monad` を継承する、それぞれの特徴を持つクラスという認識です。要するに結合可能で失敗も表せる型です。

リストの例としては以下の通りです。

```hs
> mzero :: [Int]
[]
> [1, 2, 3] `mplus` [4, 5, 6]
[1,2,3,4,5,6]
>
```

`Parser a` を `MonadPlus` のインスタンスにするには以下のように定義します。

```hs
instance MonadPlus Parser where
  mzero = mempty
  mplus = mappend
```

`Parser a` を `MonadPlus` のインスタンスにすると、以下のように書き下すことができます。

```hs
> :m + Control.Monad
> :{
| startsWithX :: Parser Char
| startsWithX = do
|   x <- item
|   guard $ x == 'x'
|   return x
| :}
> parse startsWithX "abc"
[]
> parse startsWithX "xyz"
[('x',"yz")]
```

上記のように `guard` 関数を用いて失敗を表せるという特徴と、`mplus` による結合が `MonadPlus` の特徴です。

[^why-tuple-list]: 結果型がリストであるということは、複雑な式をリスト内包表記で書くことができ、リスト自体が様々な型クラスのインスタンスで非常に多くの性質を兼ね備え、豊富に用意された便利なリスト用関数が利用でき、なおかつリストのリテラルは書きやすい、というメリットを享受できます
[^applicative-style-recommendations]: [Applicativeのススメ - あどけない話](https://kazu-yamamoto.hatenablog.jp/entry/20101211/1292021817)の一読をお勧めします
[^please-tell-me-how-to-use-some-and-many]: `some` と `many` をどのように活用すべきかご存知の方はコメントお願いします