Haskell

作って理解する Haskell の Monad

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

MonadApplicative がベースに、Applicative は Functor がベースになっています。つまり、Monad を理解するには Functor と Applicative をちゃんと理解しておく必要があります。

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

Functor、Applicative、Monad の復習

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

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

結論

  1. Functor は Functor タイプクラスを実装したデータタイプ
  2. Applicative は Applicative タイプクラスを実装したデータタイプ
  3. Monad は Monad タイプクラスを実装したデータタイプ
  4. Maybe は 3 つすべてを実装しており、つまり Functor であり Applicative であり Monad でもある

これら 3 つは何が違うのか?

recap.png

  • Functors: fmap または <$> を使用してラップされた値に関数を適用できる
  • Applicatives: <*> または 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

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

モナドを実装してみる

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

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

data List a = Nil | Cons a (List a)
  deriving (Eq, Show)

[1, 2, 3] 相当はこのデータ型だと Cons 1 $ Cons 2 $ Cons 3 $ Nil となります。全然違うように見えますが、リストの記述を脱糖すると 1:2:3:[] となり、構造としては似ていることがわかります。

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

Functor の実装

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

instance Functor List where
  fmap f Nil = Nil
  fmap f (Cons x l) = Cons (f x) (fmap f l)

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

Applicative の実装

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

infixr 5 +++

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

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

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

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

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

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

Monad の実装

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

instance Monad List where
  Nil >>= f = Nil
  Cons 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)

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

list1 :: List Int
list1 = Cons 1 $ Cons 2 $ Cons 3 $ Nil

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

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

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

すべて True が出力され、今回作成したモナドはモナド則を満たしていることがわかりました。

まとめ

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

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

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