日記 (2019 年 3 月 11 日)

3 月 11 日では、 ある意味でモナドを一般化したものも言える Arrow という型クラスについて扱いました。 Haskell には、 この Arrow にさらに構造を付け加えた型クラスがいくつか定義されています。 ここでは、 その 1 つである ArrowApply に触れたいと思います。

まずは Arrow や計算からは離れて、 具体的な関数の話から始めます。 a 型から b 型への関数 (つまり a -> b 型の値) fa 型の値 x から成るタプルがあったとします。 すると、 fx に適用することで、 b 型の値を得ることができます。 ここで行った 「関数と値からそれらを適用した結果の値を得る」 という操作も、 また関数になります。 具体的には、 (a -> b, a) -> b 型をもちます。

これを計算に一般化すると、 a 型から b 型への計算と a 型の値が与えれたとき、 それを実行した結果である b 型の値を得ることそのものもまた計算になる、 と言えます。 この計算と値から実行結果を得る計算は、 考えている Arrow クラスのインスタンスを h と書くことにすれば、 h (h a b, a) b と書くことができます。 この構造を追加した Arrow クラスが ArrowApply クラスです。

class Arrow h => ArrowApply h where
-- 計算と値から結果を得るという計算
app :: h (h a b, a) b

前回述べた通り、 モナドはクライスリ圏を作ることで Arrow のインスタンスにできました。 これはさらに ArrowApply のインスタンスにもなります。 ただ関数適用するだけです。

instance Monad m => ArrowApply (Kleisli m) where
-- 計算と値から結果を得るという計算
app :: (a -> m b, a) -> m b
app (f, x) = f x

ということで、 Monad のインスタンス m からは ArrowApply のインスタンス Kleisli m が作れるわけです。 実はこれは逆方向もできて、 ArrowApply のインスタンス h から Monad のインスタンスを作ることができます。 これには ArrowMonad h という名前が付いています。

type ArrowMonad h b = h () b -- () はユニット型

実際、 以下のように実装できます。

instance Arrow h => Monad (ArrowMonad h) where
-- リターン
return :: a -> h () a
return x = arr (const x)
-- バインド
(>>=) :: h () a -> (a -> h () b) -> h () b
s >>= f = s >>> arr f' >>> app
where
f' :: a -> (h () b, ())
f' x = (f x, ())

>>= の定義の方が若干分かりづらいので、 型に関して少し補足しておきます。 まず、 sh () a 型の計算です。 次に、 where の中で f' を定義しているのですが、 これは a -> (h () b, ()) 型の関数で、 これを arr によって h a (h () b, ()) 型の計算に変換しています。 最後の app は、 ここでは h (h () b, ()) b 型の計算として利用しています。 >>= の定義ではこれら 3 つの計算を順に合成しているわけですが、 合成の順に h () a 型, h a (h () b, ()) 型, h (h () b, ()) b 型となっているので、 正しく合成することができ、 最終的に h () b 型の計算が得られます。

ということで、 細かい話を省略すれば、 MonadArrowApply はほぼ同じ構造をもっているということになります。 言い換えれば、 MonadArrowApply はともに、 計算の概念を関数としてどう定式化するかという問いに対して、 それぞれ異なる視点を与えているということになるわけです。

追記 (2019 年 3 月 16 日)

MonadArrowApply が等価であることを数学的に示す PDF を書き始めました。 ここから見られます。