Category から Arrow へ

[(>>=) を (>=>) に書き換える](http://qiita.com/CyLomw/items/a874cee33c69653f53c6 "(>>=) を (>=>) に書き換える") ← 前の記事

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

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

次の記事 → まだないよ

# 書き換え再び

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

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

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

```hs
\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)]` に書き換えようと思うと，なかなかうまくいきません．


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

```hs
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` を用いて書け，

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

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

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

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

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

# `NonDet` 版の `(&&&)` ？

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

```hs
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` モジュール[^1]内で定義されています．
とりあえず定義を見てみましょう．

```hs: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`, `(***)`, `(&&&)` にはデフォルト実装が存在します[^2]．そのため，最低限 `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` は

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

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

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

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

```hs
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` は

```hs 
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` はリスト内包表記を用いて次のように書くことができます．

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

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

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

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

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

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

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

```hs
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`

```hs: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` となるので

```hs:ghci
ghci> app ((*10), 5)
50
```

のようになります．

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

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

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

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

ということです．

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

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

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

## `ArrowChoice`

```hs: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. 拡張則
1. 関手則
1. 交換則
1. 単位則
1. 結合則

## `ArrowLoop`

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

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

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

1. 拡張則
1. 左結合則
1. 右結合則
1. 滑り込み則
1. 消失則
1. 重合則

## `ArrowZero` と `ArrowPlus`

```hs: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` 記法のように，アローにもアロー記法というものがあります[^4]．
ポイントフリースタイルでありモナド以上に書きにくいアローが，アロー記法を用いると楽に書けることがあります．

## アロー変換子

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

# あとがき



# 参考文献

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

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

# 注釈

[^1]: `Control.Arrow` モジュールは `base` パッケージに含まれています．
[^2]: `second` のデフォルト実装内にある `~` という演算子は「不可反駁パターン」を表します．この演算子がついたパターンマッチは必ず成功します．興味がある人はググってください．
[^3]: 後のためにわざとリストモナドを使って書き直しています．
[^4]: GHC では `Arrows` 拡張を用いることでアロー記法を使用できるようになります．