Avendia19
English

日記 (2019 年 3 月 11 日)

モナドは、 副作用のある計算を純粋な関数として扱うために利用されるものでした。 具体的には、 何らかの種類の副作用を表すモナドを m で表すとすると、 a 型の値を受け取って副作用を生じつつ b 型の値を返す関数は、 a -> m b 型として実現されるのでした。 このような形の関数は、 特別に 「アクション」 と呼ばれることがあります。

アクションが 2 つあったら、 (型が合っていればですが) それらを順番に実行したくなりますし、 順番に実行するというアクションが作れるべきです。 つまり、 a -> m b 型のアクションと b -> m c 型のアクションがあったら、 a -> m c 型のアクションが得られるべきだということです。 実際、 そのような関数は標準ライブラリで定義されています。

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g

これをもっと一般化すると、 a 型の値から b 型の値を生み出す何らかの 「計算」 という概念があり、 (型が合っている) 2 つの計算からそれらを繋ぎ合わせた新たな計算を作れる、 と言えます。 モナドの例ではアクション (a -> m b 型) が計算に相当しますし、 副作用のない普通の関数 (a -> b 型) も計算の一種と思えます。

ここで注意ですが、 「関数」 と 「アクション」 と 「計算」 はここではそれぞれ別の概念を表す用語として使っています。 「関数」 というのは、 単に a -> b という形の型の値のことです。 また、 「アクション」 というのは、 あるモナド m に対して、 a -> m b という形の型の値のことを指します。 「計算」 はこれらを含むより広い概念で、 ある値を受け取ってそこから何らかの値を生み出す抽象的な枠組みです。

さて、 この計算という概念を Haskell 上の型クラスとして表現したのが Category クラスです。

class Category h where
-- 恒等計算
id :: h a a
-- 計算の繋ぎ合わせ
(.) :: h b c -> h a b -> h a c

h a b 型の値というのが a 型の値から b 型の値を生み出す計算を表します。 さらに、 . は 2 つの計算を合成する演算子で、 id は 「何もしない」 を表す計算です。 ・・・うーん、 思いっ切り圏ですね。

さて、 すでに述べたように、 モナド m 上のアクションは計算だと思えます。 アクションを計算だと思った場合、 a 型から b 型への計算の型は a -> m b 型として実現されます。 つまり、 h a ba -> m b になるような型コンストラクタ h を作れば良いことになります。 これには Kleisli m という名前が付いています。

なお、 実際にはデータ型として定義されていますが、 ここでは見やすさを重視して型シノニムにしておきます。 型シノニムに対してインスタンス宣言をする場合は、 GHC の TypeSynonymInstances 拡張を有効にしておく必要があるので、 注意してください。

type Kleisli m a b = a -> m b

すると、 以下のように Kleisli mCategory のインスタンスにできます。

instance Monad m => Category (Kleisli m) where
-- 恒等計算
id :: a -> m a
id = return
-- 計算の繋ぎ合わせ
(.) :: (b -> m c) -> (a -> m b) -> (a -> m c)
g . f = g <=< f

クライスリ圏は純粋な圏論でも重要な役割を果たしていて、 有名なところでは、 全てのモナドが関手の随伴対から得られることの証明に使いますね。

ちなみに、 計算の合成にはより向きが分かりやすい別名が付いています。 こちらの記号には逆向きもあります。

-- 右から左への合成
(<<<) :: Category h => h b c -> h a b -> h a c
(<<<) = (.)
-- 左から右への合成
(>>>) :: Category h => h a b -> h b c -> h a c
(>>>) = flip (.)

さて、 モナドに関しては、 普通の関数をアクションに変換することができました。 アクションを一般化した計算に関しても、 アクションの場合と同じように、 普通の関数を計算に変換する構造が付いていれば便利です。 また、 2 つの計算 f, g があるときに、 タプルとして与えられた 2 つの値の一方に f を実行して他方に g を実行し、 その結果からなる新たなタプルを得るという計算が自然に考えられますが、 このような計算も作れると便利です。 並列に計算を実行するイメージですね。

関数を計算に変換する機能と 2 つの計算を並列に実行する計算を作る機能を兼ね備えたのが Arrow クラスです。

class Category h => Arrow h where
-- 関数を計算へ持ち上げ
arr :: (a -> b) -> h a b
-- 計算を並列実行する計算を作成
(***) :: h a b -> h c d -> h (a, c) (b, d)

具体例として、 モナドから作ったクライスリ圏の場合を見てみましょう。 関数をアクションに変換したかったら、 値に関数を適用した後に文脈で包めば良いだけです。 また、 モナドの範囲内 (do 構文の中) であれば、 アクションは普通の関数のように値を取り出せるので、 2 つのアクションを同時に実行するのも簡単です。

instance Monad m => Arrow (Kleisli m) where
-- 関数を計算へ持ち上げ
arr :: (a -> b) -> (a -> m b)
arr f = return . f
-- 計算を並列実行する計算を作成
(***) :: (a -> m b) -> (c -> m d) -> ((a, c) -> m (b, d))
f *** g = \(x, y) -> do {s <- f x; t <- g y; return (s, t)}

Arrow クラスは Category クラスを拡張しているので、 恒等計算があります。 これを用いることで、 タプルで与えられた 2 つの値のうち一方にのみある計算を実行するという計算を作ることもできます。 このような関数も Arrow クラスに定義されています。

class Category h => Arrow h where
-- 左側に計算を実行
first :: h a b -> h (a, c) (b, c)
first = (*** id)
-- 右側に計算を実行
second :: h c d -> h (a, c) (a, d)
second = (id ***)

モナドには do 記法という手続き型っぽくアクションの実行が書ける特殊な構文が用意されていました。 実は、 Arrow に関しても似たような記法をできるように、 GHC では Arrows 拡張というものが提供されています。 これを有効にすると、 だいたい以下のような構文が許されるようになります。

f = proc x -> do -- a を仮引数とする計算 f を定義 (proc はラムダ式のようなもの)
y <- g -< x -- 計算 g に x を渡して実行して結果を y に格納 (<- と -< に注意)
z <- h -< (x, y) -- 計算 h に (x, y) を渡して実行して結果を z に格納
returnA -< z -- 値を返すときは returnA を使う

追記 (2019 年 3 月 11 日)

3 月 11 日に続きます。