Category から Arrow へ

(>>=) を (>=>) に書き換える ← 前の記事

今まで使ってきた Category 型クラスを強化した， Arrow 型クラスについて見ていきます．

※この記事はだいぶん未完成ですが，暫く更新できそうにないため書いたところまで一旦公開します．Arrow だけに許してね．

次の記事 → まだないよ

書き換え再び

以下の式を (>=>) を用いて書き換えることを考えてみます．

\x -> ([1..x] >>= \y -> [y..x])

f = \t -> [1..t], g = \y -> [y..x] と置くと，

\x -> (f x >>= g)

となります．

前回の中級の問題 \x -> (Just (x * 2) >>= \y -> Just (y * x)) と同じように考えると，まずやるべきことは f を結果と一緒に自分の引数を返すような函数 f' に書き換えることです．
その際，(&&&) という演算子 (函数) を使うことによって f を簡単に f' に書き換えられるのでした．

しかし，今回はちょっと状況が違います．

前回は Maybe モナドだったので

f :: Num t => t -> Maybe t から
f' :: Num t => t -> Maybe (t, t) でした．

今回はリストモナドなので

f :: (Num t, Enum t) => t -> [t] から
f' :: (Num t, Enum t) => t -> [(t, t)]

となるでしょう．

しかし，f = \t -> [1..t] を前回定義した (&&&) で f' :: (Num t, Enum t) => t -> [(t, t)] に書き換えようと思うと，なかなかうまくいきません．

例えば前回定義した (&&&) を用い，次のように書いたとします．

f' = [(\t -> [1..t]) &&& id]

しかしこれだと f' :: (Num t, Enum t) => [t -> ([t], t)] となってしまいます．

f' = (\t -> [1..t]) &&& id

としても，f' :: (Num t, Enum t) => t -> ([t], t) ですし，

f' = (\t -> [1..t]) &&& (\t -> [t])

でも f' :: (Num t, Enum t) => t -> ([t], [t]) でだめです．

そこで，リストを返す二つの函数をとる (&&&) の別種 (&&&&) を作成してみます．
即ち，(&&&&) :: (b -> [c]) -> (b -> [c']) -> b -> [(c, c')] のようなリストの場合専用の演算子を作ってみます．

"リストを返す函数" 用演算子 (&&&&)

ということで，作ってみました．

(&&&&) :: (b -> [c]) -> (b -> [c']) -> b -> [(c, c')]
f &&&& g = \x -> [(t, s) | t <- f x, s <- g x]

この演算子は次のように動きます．

ghci

ghci> (\x -> [x * 2, x * 3]) &&&& (\x -> [x, -x]) $ 10
[(20,10),(20,-10),(30,10),(30,-10)]

この演算子を用いると f' は次のように書けます．

f' = (\t -> [1..t]) &&&& (\t -> [t])

ちなみに \t -> [t] はリストモナドの return の定義なので

f' = (\t -> [1..t]) &&&& return

と書けます．

この定義では確かに f' :: (Num t, Enum t) => t -> [(t, t)] となっています．

また，g' は前回と同様 g' = \(y, x) -> [y..x] でよいでしょう．

以上より，\x -> (f x >>= g) は次のように f', g を用いて書け，

\x -> (f' x >>= g')

f', g' を定義前の形に戻してみると

\x -> ( ((\t -> [1..t]) &&&& return) x >>= (\(y, x) -> [y..x]) )

これで (>=>) の定義の形に持ち込むことができたので，次のようになります．

((\t -> [1..t]) &&&& return) >=> (\(y, x) -> [y..x])

NonDet 版の (&&&) ？

ところで，以前 b -> [c] のようにリストを返す関数を「非決定性計算」と呼び，非決定性計算を表す NonDet i o 型を作成したのでした．さらに NonDet を合成するためにこれを Category という型クラスのインスタンスにしたのでした．

import Control.Category hiding (id, (.))
import qualified Control.Category as Cat
import Control.Monad

newtype NonDet i o = NonDet { runNonDet :: i -> [o] }

instance Category NonDet where
    id = NonDet return
    (NonDet f) . (NonDet g) = NonDet $ f <=< g

ここでちょっと考えてみます．先ほど作った (&&&&) は，前回定義した (&&&) の「リストを返す函数版」，即ち「非決定性計算版」でした．

つまり，NonDet カテゴリーに対して使える (&&&) のような演算子も作ることができるのではないでしょうか．

そしてさらに， NonDet の合成の実装は (>=>) の逆向き版の (<=<) を用いていました．

そうすると，先ほどの (>=>) と (&&&&) を使った式は，NonDet の合成 (>>>) と 「NonDet 版の (&&&) 演算子」を使って書けそうな気がしてきます．

さらにさらに，NonDet 以外のカテゴリーについても (&&&) のようなものを考えることができるのではないでしょうか．例えば Possible とか，Kleisli m とか．

さて，ここで登場するのが Arrow 型クラスです．

Arrow 型クラス

ついに登場しました，Arrow です！
Arrow 型クラスは Control.Arrow モジュール¹内で定義されています．
とりあえず定義を見てみましょう．

Control.Arrow

class Category a => Arrow a where
    arr :: (b -> c) -> a b c

    first :: a b c -> a (b,d) (c,d)

    second :: a b c -> a (d,b) (d,c)
    second f = arr swap >>> first f >>> arr swap
      where
        swap :: (x,y) -> (y,x)
        swap ~(x,y) = (y,x)

    (***) :: a b c -> a b' c' -> a (b,b') (c,c')
    f *** g = first f >>> second g

    (&&&) :: a b c -> a b c' -> a b (c,c')
    f &&& g = arr (\b -> (b,b)) >>> f *** g

まず，class Category a => Arrow a where となっているので，Arrow 型クラスのインスタンスを作ろうと思ったらまず Category のインスタンスにする必要があることがわかります．

Arrow 型クラスは，5 つの函数 arr, first, second, (***), (&&&) を定義しています．

しかしよく見ると，second, (***), (&&&) にはデフォルト実装が存在します²．そのため，最低限 arr と first だけを実装すればよいことがわかります．

arr

函数 arr :: Arrow a => (b -> c) -> a b c は，Applicative の pure や Monad の return のような存在です．

pure :: Applicative f => a -> f a は普通の値を引数にとり，アプリカティブ値にして返しました．
return :: Monad m => a -> m a は普通の値を引数にとり，モナド値にして返しました．
同様に，arr :: Arrow a => (b -> c) -> a b c は普通の函数を引数にとり，Arrow にして返します．

例えば NonDet について考えてみましょう．
もし NonDet が Arrow 型クラスのインスタンスになるとすれば，arr は

arr :: (b -> c) -> NonDet b c

という型になります．実装はどうなるでしょうか．
普通の函数 f :: b -> c が「非決定性計算」になるとすれば，それは単純に返り値を [] で囲むことになりそうです．即ち，次のようになるでしょう．

arr f = NonDet (\x -> [f x])

値を単純に [] に入れて返すリストモナドの return を使うと，次のようにも書けます．

arr f = NonDet (return . f)

first

函数 first :: Arrow a => a b c -> a (b, d) (c, d) は，ペアの一番目の要素にのみ計算を適用します．

たとえば a を (->) に置き換えてみると，first :: b -> c -> (b, d) -> (c, d) となります．これは前回作った first 函数の型とまったく同じです．(なんとなくわかっているとは思いますが，実は普通の函数も Arrow 型クラスのインスタンスです．)

もし NonDet が Arrow 型クラスのインスタンスになるとすれば，first は

first :: NonDet b c -> NonDet (b, d) (c, d)

という型になります．
これの実装を考えてみましょう．

簡単にするために，とりあえず NonDet b c ではなく b -> [c]，NonDet (b, d) (c, d) ではなく (b, d) -> [(c, d)]として考えてみます．

即ち，f :: b -> [c] という函数を g :: (b, d) -> [(c, d)] という函数に変換することについて考えます．

具体的に考えてみましょう．例えば，f x = [y_1, y_2, ..., y_n] とします．
すると，g (x, z) = [(y_1, z), (y_2, z), ..., (y_n, z)] となってほしいわけです．first なので，ペアの二つ目の要素については影響を与えないことにします．

このような g はリスト内包表記を用いて次のように書くことができます．

g (x, z) = [(y, z) | y <- f x]

また，リスト内包表記は次のようにリストモナドで書き換えることができます³．

g (x, z) = f x >>= (\y -> return (y, z))

これで f :: b -> [c] という函数を g :: (b, d) -> [(c, d)] という函数に変換することができました．あとは NonDet で包んであげることで，NonDet に対する first は次のように書けます．

first (NonDet f) = NonDet (\(x, z) -> f x >>= (\y -> return (y, z)))

NonDet を Arrow のインスタンスにする

さて，NonDet に対する arr, first を作ることができたので，実際に NonDet を Arrow のインスタンスにしてみましょう．

import Control.Arrow
import Control.Category hiding (id, (.))
import qualified Control.Category as Cat
import Control.Monad

newtype NonDet i o = NonDet { runNonDet :: i -> [o] }

instance Category NonDet where
    id = NonDet return
    (NonDet f) . (NonDet g) = NonDet $ f <=< g

instance Arrow NonDet where
    arr f = NonDet (return . f)
    first (NonDet f) = NonDet (\(x, z) -> f x >>= (\y -> return (y, z)))

めでたく NonDet アローが誕生しました．second, (***), (&&&) 函数についてはデフォルト実装がありますが，どのような動作をするかちょっと動かしてみましょう．

second

(考え中)

(***)

(考え中)

(&&&)

(考え中)

(考え中)

Arrow 則

(考え中)

Category 則の 2 つ + 7 つ

Arrow のなかまたち

Control.Arrow モジュールを除いてみると，Arrow のいろいろな仲間たちを見つけることができます．ここでは，そんな Arrow の仲間たちをちょっとだけ紹介したいと思います．

ArrowApply

Control.Arrow

class Arrow a => ArrowApply a where
    app :: a (a b c, b) c

ArrowApply 型クラスは函数 app を提供します．
函数 app は，(計算 f, 値 x) なるタプルをとって f に x を入力した結果を返す計算となります．

例えば通常の函数の場合は app :: (b -> c, b) -> c となるので

ghci

ghci> app ((*10), 5)
50

のようになります．

ArrowApply のインスタンスにするためには，3 つの ArrowApply 則を満たす必要があります．

1. 合成則
2. 簡約則
3. 外延性

そして，ArrowApply は実は Monad と同様の能力を持つことが知られています．
つまり，

• ArrowApply でできることは Monad にもできる．
• Monad にできることは ArrowApply にもできる．
• Monad にできることは Arrow にもできる．
• Arrow にはできて，Monad にはできないことがある．

ということです．

実は Kleisli アローは ArrowApply の型クラスなので，今までやってきた Kleisli アローを使った計算はすべてモナドで事足りるのでした．

例えばオートマトンや電子回路のシミュレーション，並列アルゴリズムなどはモナドでは力不足である (即ち ArrowApply 型クラスのインスタンスになれない) ので Arrow の力を借りるらしいです．

また，任意の ArrowApply のインスタンスは後述する ArrowChoice のインスタンスになることができます．

ArrowChoice

Control.Arrow

class Arrow a => ArrowChoice a where
    left :: a b c -> a (Either b d) (Either c d)

    right :: a b c -> a (Either d b) (Either d c)
    right f = arr mirror >>> left f >>> arr mirror
      where
        mirror :: Either x y -> Either y x
        mirror (Left x) = Right x
        mirror (Right y) = Left y

    (+++) :: a b c -> a b' c' -> a (Either b b') (Either c c')
    f +++ g = left f >>> right g

    (|||) :: a b d -> a c d -> a (Either b c) d
    f ||| g = f +++ g >>> arr untag
      where
        untag (Left x) = x
        untag (Right y) = y

ArrowChoice 型クラスは入力によって条件分岐できる計算を表し，条件分岐するためのいくつかの函数を提供します．

ArrowChoice のインスタンスにするためには，5 つの ArrowChoice 則を満たす必要があります．

1. 拡張則
2. 関手則
3. 交換則
4. 単位則
5. 結合則

ArrowLoop

Control.Arrow

class Arrow a => ArrowLoop a where
    loop :: a (b,d) (c,d) -> a b c

ArrowLoop 型クラスは出力を入力に戻す (フィードバック) 函数 loop を提供します．

ArrowLoop のインスタンスにするためには，6 つの ArrowLoop 則を満たす必要があります．

1. 拡張則
2. 左結合則
3. 右結合則
4. 滑り込み則
5. 消失則
6. 重合則

ArrowZero と ArrowPlus

Control.Arrow

class Arrow a => ArrowZero a where
    zeroArrow :: a b c

class ArrowZero a => ArrowPlus a where
    (<+>) :: a b c -> a b c -> a b c

Monad に対する MonadPlus のようなもので，モノイドの性質を併せ持つアローを表す型クラスです．

アロー記法

モナドの do 記法のように，アローにもアロー記法というものがあります⁴．
ポイントフリースタイルでありモナド以上に書きにくいアローが，アロー記法を用いると楽に書けることがあります．

アロー変換子

モナドに対するモナド変換子のように，アローに対するアロー変換子なるものが存在するらしいです．

あとがき

参考文献

Jeremy Gibbons and Oege de Moor 編，山下伸夫訳 「関数プログラミングの楽しみ」 (オーム社) 2010, 215-238

Miran Lipovača 著，田中英行・村主崇行訳 「すごい Haskell たのしく学ぼう！」 (オーム社) 2012

注釈

1. Control.Arrow モジュールは base パッケージに含まれています． ↩

2. second のデフォルト実装内にある ~ という演算子は「不可反駁パターン」を表します．この演算子がついたパターンマッチは必ず成功します．興味がある人はググってください． ↩

3. 後のためにわざとリストモナドを使って書き直しています． ↩

4. GHC では Arrows 拡張を用いることでアロー記法を使用できるようになります． ↩