日記 (2019 年 3 月 11 日)
3 月 11 日では、 ある意味でモナドを一般化したものも言える Arrow という型クラスについて扱いました。
Haskell には、 この Arrow にさらに構造を付け加えた型クラスがいくつか定義されています。
ここでは、 その 1 つである ArrowApply に触れたいと思います。
まずは Arrow や計算からは離れて、 具体的な関数の話から始めます。
a 型から b 型への関数 (つまり a -> b 型の値) f と a 型の値 x から成るタプルがあったとします。
すると、 f を x に適用することで、 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, ())
>>= の定義の方が若干分かりづらいので、 型に関して少し補足しておきます。
まず、 s は h () 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 型の計算が得られます。
ということで、 細かい話を省略すれば、 Monad と ArrowApply はほぼ同じ構造をもっているということになります。
言い換えれば、 Monad と ArrowApply はともに、 計算の概念を関数としてどう定式化するかという問いに対して、 それぞれ異なる視点を与えているということになるわけです。
追記 (2019 年 3 月 16 日)
Monad と ArrowApply が等価であることを数学的に示す PDF を書き始めました。
ここから見られます。