知らないモナドに遭遇しても慌てないために、モナドを自分で作って理解してみることにしました。
Monad は Applicative がベースに、Applicative は Functor がベースになっています。つまり、Monad を理解するには Functor と Applicative をちゃんと理解しておく必要があります。
まずは Functor、Applicative、Monad を復習しておきましょう。
Functor、Applicative、Monad の復習
Functor、Applicative、Monad の概要を理解するには以下のリンクが助けになります。
以下に引用して翻訳します。
結論
- Functor は
Functorタイプクラスを実装したデータタイプ- Applicative は
Applicativeタイプクラスを実装したデータタイプ- Monad は
Monadタイプクラスを実装したデータタイプMaybeは 3 つすべてを実装しており、つまり Functor であり Applicative であり Monad でもあるこれら 3 つは何が違うのか？
- Functor:
fmapまたは<$>を使用してラップされた値に関数を適用できる- Applicative:
<*>またはliftAを使用してラップされた関数をラップされた値に適用できる- Monad:
>>=またはliftMを使用してラップされた値に、ラップされた値を返す関数を適用できる
図と箇条書きを見比べると、Functor、Applicative、Monad の特徴が見えてきませんか？
Functor、Applicative、Monad のタイプクラス
定義は以下のような感じです。
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
なるほど、それぞれのタイプクラスはだいたい理解できました。
モナドを実装してみる
実装するモナドは簡単すぎず難しすぎないリストモナドを再定義することにしてみました。
まずはリストの定義です。
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 のインスタンスにするには以下のようにします。
instance Functor List where
fmap f Nil = Nil
fmap f (x ::: l) = (f x) ::: (fmap f l)
再帰的にすべての要素に関数を適用していくだけで、ここはまだあまり難しくはないですね。
Applicative の実装
List を Applicative のインスタンスにするには以下のようにします。
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 のインスタンスにするには以下のようにします。
instance Monad List where
Nil >>= f = Nil
x ::: t >>= f = f x +++ (t >>= f)
return = pure
>>= に与えられる関数は、ラップされていない値を取りラップされた値を返し、それを再帰的にリストに適用しつつリストを再構築することになります。ここでも Applicative で使用した +++ を用いて >>= を再帰的に定義しています。
モナド則
Monad を実装したらモナド則に則っているか確認しなければなりません。以下の 3 式が True になる必要があります。
(return x) >>= f == f xm >>= return == m(m >>= f) >>= g == m >>= (\x -> f x >>= g)
こんな感じで確認します。
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 が出力されていることがわかります。
まとめ
今回作成したのは独自リストのデータ型なので、すべてのタイプクラスでリストに関数を再帰的に適用することができれば実現できることがわかりました。おそらく他のデータ型でも基本的な関数の適用方法はすべてのタイプクラスで共通になると思います。また、今回の +++ のような補助関数が必要になることもあると思いますが、もともとリストの結合関数はデータ型として必要であり、他のデータ型でもデータが必要とする関数を用意することでタイプクラスの実装に使用できそうな気がします。
皆さんも一度自身でモナドを実装してみてはいかがでしょうか？ なお、今回のソースコードは以下に公開されています。
以下は今回のモナドの実装方法とは全く次元の異なる内容ですが、モナドの実装方法には様々な方法があるんだな、と示してくれる良いエントリです。