作って理解する Haskell の Monad

知らないモナドに遭遇しても慌てないために、モナドを自分で作って理解してみることにしました。

[Monad](http://hackage.haskell.org/package/base-4.10.0.0/docs/Control-Monad.html#t:Monad) は [Applicative](http://hackage.haskell.org/package/base-4.10.0.0/docs/Control-Applicative.html#t:Applicative) がベースに、Applicative は [Functor](http://hackage.haskell.org/package/base-4.10.0.0/docs/Data-Functor.html#t:Functor) がベースになっています。つまり、Monad を理解するには Functor と Applicative をちゃんと理解しておく必要があります。

まずは Functor、Applicative、Monad を復習しておきましょう。

# Functor、Applicative、Monad の復習

Functor、Applicative、Monad の概要を理解するには以下のリンクが助けになります。

* [Functors, Applicatives, And Monads In Pictures - adit.io](http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html)

以下に引用して翻訳します。

<!--
> ### Conclusion
> 
> 1. A functor is a data type that implements the `Functor` typeclass.
> 2. An applicative is a data type that implements the `Applicative` typeclass.
> 3. A monad is a data type that implements the `Monad` typeclass.
> 4. A `Maybe` implements all three, so it is a functor, an applicative, and a monad.
> 
> What is the difference between the three?
> 
> ![recap.png](https://qiita-image-store.s3.amazonaws.com/0/31613/378d3c65-fed9-5aed-35de-d85dfbc0c690.png)
> 
> * __functors__: you apply a function to a wrapped value using `fmap` or `<$>`
> * __applicatives__: you apply a wrapped function to a wrapped value using `<*>` or `liftA`
> * __monads__: you apply a function that returns a wrapped value, to a wrapped value using `>>=` or `liftM`

以下のように述べています。
-->

> ### 結論
> 
> 1. Functor は `Functor` タイプクラスを実装したデータタイプ
> 2. Applicative は `Applicative` タイプクラスを実装したデータタイプ
> 3. Monad は `Monad` タイプクラスを実装したデータタイプ
> 4. `Maybe` は 3 つすべてを実装しており、つまり Functor であり Applicative であり Monad でもある
> 
> これら 3 つは何が違うのか？
> 
> ![recap.png](https://qiita-image-store.s3.amazonaws.com/0/31613/378d3c65-fed9-5aed-35de-d85dfbc0c690.png)
> 
> * __Functor__: `fmap` または `<$>` を使用してラップされた値に関数を適用できる
> * __Applicative__: `<*>` または `liftA` を使用してラップされた関数をラップされた値に適用できる
> * __Monad__: `>>=` または `liftM` を使用してラップされた値に、ラップされた値を返す関数を適用できる

図と箇条書きを見比べると、Functor、Applicative、Monad の特徴が見えてきませんか？

## Functor、Applicative、Monad のタイプクラス

定義は以下のような感じです。

```hs
class Functor f where
  -- | fmap は上記説明通りの定義になってますね
  fmap :: (a -> b) -> f a -> f b

class Functor f => Applicative f where
  pure :: a -> f a
  -- | <*> は上記説明通りの定義になってますね
  (<*>) :: f (a -> b) -> f a -> f b
  liftA2 :: (a -> b -> c) -> f a -> f b -> f c
  (*>) :: f a -> f b -> f b
  (<*) :: f a -> f b -> f a

class Applicative m => Monad m where
  -- | >>= は上記説明通りの定義になってますね
  (>>=) :: forall a b. m a -> (a -> m b) -> m b
  (>>) :: forall a b. m a -> m b -> m b
  return :: a -> m a
  -- ! !!!
  fail :: String -> m a
```

なるほど、それぞれのタイプクラスはだいたい理解できました。

# モナドを実装してみる

実装するモナドは簡単すぎず難しすぎないリストモナドを再定義することにしてみました。

まずはリストの定義です。

```hs
infixr 6 :::

data List a = Nil | (:::) a (List a) deriving Eq

instance Show a => Show (List a) where
  show x = "[" ++ showList' x ++ "]"

showList' :: Show a => List a -> String
showList' Nil = ""
showList' (x ::: Nil) = show x
showList' (x ::: xs) = show x ++ "," ++ showList' xs
```

`[1, 2, 3]` 相当はこのデータ型だと `1 ::: 2 ::: 3 ::: Nil` となります。リストの記述を脱糖すると `1:2:3:[]` となり、構造としてはかなり似ていることがわかります。なお、List を `Show` クラスのインスタンスにしているのは、表示した際の見た目だけで、Monad とは関係ありません。また、deriving も後の検証で使用するだけで Monad とは直接関係ありません。

このデータ型のポイントは、リストの終わりを示す `Nil` があることと、`:::` の最初の要素が値で最後の要素は再帰であることです。`Nil` にはどのような関数を適用しても Nil を返すこと、関数を適用するのは `:::` の最初の要素のみで、最後の要素は再帰的に処理すれば `Nil` に到達するまで最初の要素に関数を適用し続けること、この 2 点を気にしながら実装を進めていけば良い感じになりそうです。

## Functor の実装

List を Functor のインスタンスにするには以下のようにします。

```hs
instance Functor List where
  fmap f Nil = Nil
  fmap f (x ::: l) = (f x) ::: (fmap f l)
```

再帰的にすべての要素に関数を適用していくだけで、ここはまだあまり難しくはないですね。

## Applicative の実装

List を Applicative のインスタンスにするには以下のようにします。

```hs
infixr 5 +++

(+++) :: List a -> List a -> List a
Nil +++ l = l
l +++ Nil = l
x ::: Nil +++ l = x ::: l
x ::: t +++ l = x ::: (t +++ l)

instance Applicative List where
  pure x = x ::: Nil
  Nil <*> _ = Nil
  f ::: fs <*> m = (f <$> m) +++ (fs <*> m)
```

自作リストを Applicative のインスタンスにするには、ラップされた関数リストをラップされた値リストに適用して、値リストを返さなければならないわけですから、リストは結合が行える必要があります。処理をステップに分けると以下のような感じです。

`[(+1), (+10)] <*> [1, 2]` → `[2, 11] ++ [3, 12]` → `[2, 11, 3, 12]`

今回の独自リストには `:::` という `:` に相当するデータコンストラクタがありますが、上記を見ると `++` に相当する関数が必要になることがわかります。そのため、独自リスト `List` データ型のためのリスト結合関数を `+++` として実装し、それを使用して `<*>` を再帰的に定義しています。`infixr 5` と定義しているのは `++` が同様に `infixr 5` だったためです。ちなみに `(f <$> m)` は `fmap f m` と定義しても良いのですが `<$>` を使う方がイケてます[^1]。

データ型をタイプクラスのインスタンスにする場合、**タイプクラス外でも補助関数を定義しなければならないことがある**、ということがわかったのは収穫でした。

## Monad の実装

List を Monad のインスタンスにするには以下のようにします。

```hs
instance Monad List where
  Nil >>= f = Nil
  x ::: t >>= f = f x +++ (t >>= f)
  return = pure
```

`>>=` に与えられる関数は、ラップされていない値を取りラップされた値を返し、それを再帰的にリストに適用しつつリストを再構築することになります。ここでも Applicative で使用した `+++` を用いて `>>=` を再帰的に定義しています。

## モナド則

Monad を実装したらモナド則に則っているか確認しなければなりません。以下の 3 式が `True` になる必要があります。

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

こんな感じで確認します。

```hs
list1 :: List Int
list1 = 1 ::: 2 ::: 3 ::: Nil

func1 :: Int -> List String
func1 n = (show n) ::: Nil

func2 :: String -> List String
func2 s = ("(" ++ s ++ ")") ::: Nil

main :: IO ()
main = do
  print list1
  print $ (return 100 >>= func1) == func1 100
  print $ (list1 >>= return) == list1
  print $ ((list1 >>= func1) >>= func2) == (list1 >>= (\x -> func1 x >>= func2))
```

実行すると、以下のように期待するリスト表記とモナド則が満たされていることを表す `True` が出力されていることがわかります。

# まとめ

今回作成したのは独自リストのデータ型なので、すべてのタイプクラスでリストに関数を再帰的に適用することができれば実現できることがわかりました。おそらく他のデータ型でも基本的な関数の適用方法はすべてのタイプクラスで共通になると思います。また、今回の `+++` のような補助関数が必要になることもあると思いますが、もともとリストの結合関数はデータ型として必要であり、他のデータ型でもデータが必要とする関数を用意することでタイプクラスの実装に使用できそうな気がします。

皆さんも一度自身でモナドを実装してみてはいかがでしょうか？ なお、今回のソースコードは以下に公開されています。

* [satosystems/monad-practice: Monad practice on Haskell](https://github.com/satosystems/monad-practice)

以下は今回のモナドの実装方法とは全く次元の異なる内容ですが、モナドの実装方法には様々な方法があるんだな、と示してくれる良いエントリです。

* [モナドの実装いろいろ - Qiita](https://qiita.com/philopon/items/6c202200e266548275ea)

---

[^1]: [Applicativeのススメ - あどけない話](http://d.hatena.ne.jp/kazu-yamamoto/20101211/1292021817)