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

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

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

• Functor
• Applicative
• Monad
• Semigroup
• Monoid
• Alternative
• MonadPlus

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

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

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

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

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

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

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

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

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

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

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

Functor

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

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

> (+ 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 のインスタンスにするには以下のように定義します。

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 のインスタンスにすると、以下のように書き下すことができます。

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

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

Applicative

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

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

> 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 のインスタンスにするには以下のように定義します。

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 のインスタンスにすると、以下のように書き下すことができます。

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

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

> :{
| 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 は Functor の <$> と組み合わせることで威力を発揮することがわかりました。例えば最初の 3 文字を大文字にするパーサは以下のように書き下します。

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

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

Monad

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

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

> 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 のインスタンスにするには以下のように定義します。

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

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

> :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 については以下のモナド則という規則を満たしていなければなりません。

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

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

Semigroup

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

> [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 のインスタンスにするには以下のように定義します。

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 のインスタンスにすると、以下のように書き下すことができます。

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

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

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

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

Monoid

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

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

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

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

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

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

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

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

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 が利用できます³。

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

> 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 のインスタンスにするには以下のように定義します。

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

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

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

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

MonadPlus

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

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

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

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

instance MonadPlus Parser where
  mzero = mempty
  mplus = mappend

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

> :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 の特徴です。

1. 結果型がリストであるということは、複雑な式をリスト内包表記で書くことができ、リスト自体が様々な型クラスのインスタンスで非常に多くの性質を兼ね備え、豊富に用意された便利なリスト用関数が利用でき、なおかつリストのリテラルは書きやすい、というメリットを享受できます ↩

2. Applicativeのススメ - あどけない話の一読をお勧めします ↩

3. some と many をどのように活用すべきかご存知の方はコメントお願いします ↩