Arrowを理解する

これは[Haskell Advent Calendar その１](https://qiita.com/advent-calendar/2017/haskell) 8日目の記事です。

前日の記事は@nobsunさんの[Tree: 親子関係の付け替え](https://qiita.com/nobsun/items/27fe53516cbb90ba02e2)でした。

# 対象者

* すごいH読んだ
* 型とか型クラスわかる
* hlintにArrow使えって怒られたことがある
* 反駁不可パターンはわかる

# Arrowとは

プログラミングには純粋な関数ではないが、関数のような雰囲気を持った構成要素が存在する。 この記事ではこれを計算と呼ぶことにする。型クラスを使えば、こういった計算に共通する構造を見つけることで、インターフェイスを提供できる。こういった抽象度の高いインターフェイスを提供することの有用性は語るまでもないだろう。ざっくり言えば実はこれがArrowである。我々が呼吸するように使う(?)Monadもこれに類するものである。ArrowはMonadと違い、複数の入力を消費できる、入力値による選択が行える、フィードバックが可能であるという点において、Monadよりも抽象度の高い。この記事では計算に共通の構造を見つけるところから、Arrowの形式化を行っていく。

# 計算の構造を探る

 ２つの関数に値を適用してその結果を合成するadd関数を、4つの計算を扱えるように拡張してみる。

```haskell
add :: (a -> Int) -> (a -> Int) -> (a -> Int)
add f g a = f a + g a
```

## 状態変換

状態変換子は以下のような型を持つと推察できる。[^1]

[^1]: この例ではただの型シノニムだが、この型シノニムからState Monadに変換する関数mapStateがControl.Monad.State.Lazyで提供されている。

```haskell
type State s a b = (s, a) -> (s, b)
```

先程のadd関数をこの状態変換子を使えるように一般化してみよう。

```haskell
addST :: State s a Int -> State s a Int -> State s a Int
addST f g (s, b) = let (s', x) = f(s, b)
                       (s'', y) = g(s', b)
                   in (s'', x + y)
```

コードから分かるように、`f`で状態`s`を消費した後に`g`で消費したあとの状態`s'`を消費している。実装を変えれば`g`で先に状態を消費することも可能である。

## 非決定性

非決定性計算とは簡単にいえば複数の値を返す計算である。
返す値の型が同一であれば以下のように書けるであろう。

```haskell
type NonDet a b = a -> [b]
```

リストがモナドである理由はここから来ている。
状態の時と同様にadd関数を非決定性計算を使えるように一般化してみる。

```haskell
addND :: NonDet a Int -> NonDet a Int -> NonDet a Int
addND f g a = [x + y | x <- f a, y <- g a]
```

これはそれぞれの出力の要素を足し合わせているに過ぎない。

## 写像変換

データ並列アルゴリズムなどに使われる写像変換子は以下の様に表される。

```haskell
type MapTrans a b c = (a -> b) -> (a -> c)
```

`a`の値によって結果が違う関数を相互に変換すると捉えられる。
また、`a`を時間変化する値を考えれば、写像変換子は各時間における関数(振る舞い)を変換するものになる。

今までと同じようにadd関数を写像変換子を使えるように一般化してみる。

```haskell
addMT :: MapTrans a b Int -> MapTrans a b Int -> MapTrans a b Int
addMT f g m s = f m s + g m s
```

この`addMT`はそれぞれの値、時間において入力を評価し、その結果を足し合わせている。

## 単純オートマン

単純オートマンとは入力を出力と、自分自身の状態を更新する計算である。
これの型は以下のように表されるだろう。

```haskell
newtype Auto a b = A(a -> (b, Auto a b)
```

では、add関数をこの単純オートマンが使えるように一般化しよう。

```haskell
addAuto :: Auto a Int -> Auto a Int -> Auto a Int
addAuto (A f)(A g) = A(\b -> let (x, f') = f b
                                 (y, g') = g b
                             in (x + y, addAuto f' g'))
```

# これらの計算を抽象化する

今までの計算には共通の構造として、型Aをとって型Bを返すと言ってようなものがある。
例えば状態変換子であれば、(s, a)をとって、(s, b)を返していた。
また、add関数を一般化する上でこれらの計算を合成している事がわかる。

そこで次のような型クラスを定義してみよう。

```haskell
class Category a where
    idA :: a b b
    (>>>) :: a b c -> a c d -> a b d
```

`idA`は何もしない計算を、`(>>>)`は計算の合成を表す。
`idA`と`>>>`は計算の構造を保つためにも以下のような公理を満たす必要がある。

```haskell
idA >>> f = f >>> idA = f          -- 恒等性
(f >>> g) >>> h = f >>> (g >>> h)  -- 結合性
```

恒等性は何も変えないこと、結合性は計算の結合順序による変化は起こらないことを保証している。

純粋な関数がこのCategoryのインスタンスであることを確認してみよう。

```haskell
instance Category (->) where
    idA = id
    f >>> g = g . f
```

プログラミングする上で、関数と計算を合成できると嬉しいだろう。
そのために、関数を純粋な計算に変換してみる。

```haskell
arr :: (b -> c) -> a b c
```

これも計算の構造を保存する必要があるため、以下の公理を満たす必要がある。

```haskell
arr id = idA
arr (g . f) = arr f >>> arr g
```

これで関数を純粋な計算とすることができるようになったが、先に紹介した計算を一般化するにはまだ機能が足りない。
計算を入力の一部に適用したりということが必要になってくる。
これはいわゆる積で定義できる。

```haskell
(><) :: (a -> a') -> (b -> b') -> (a, b) -> (a', b')
(f >< g) ~(a, b) = (f a, g b)
```

上記ではわかりやすさのために`(->)`を使っているが、Categoryでいえば

```haskell
(***) :: a b c -> a b' c' -> a (b, b') (c, c')
```
である。(ここでは別物として`><`を`(***)`で置き換えている)

とりあえずは、この積とは`f`の入力の集合と`g`の入力の集合のタプルをそれぞれの出力の集合のタプルに変換するという意味と捉えて良い。

これは状態変換子のような計算の順序を変えると結果が変わるような構造を表すことができる。

```haskell
(f >< g) ~(a, b) = (f a, g b)
(g >< f) ~(a, b) = (g a, f b)
```

積はもっと簡単な定義として、片方だけ適用するという`first`, `second`がある。

```haskell
first :: a b c -> a (b, d) (c, d)   -- f *** idA と一緒
second :: a b c -> a (d, b) (d, c)  -- idA *** f と一緒
```

上記の`second`は`first`から簡単に導出できる上に、`(***)`も`first`, `second`の合成から簡単に導出できるので、実際には`first`のみを実装すれば良い。

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

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

なお、計算の構造を保つために、`first`は以下の公理を満たす必要がある。

```haskell
first (arr f) = arr (f >< id)                          -- 拡張
first (f >>> g) = first f >>> first g                  -- 関手
first f >>> arr (id >< g) = arr (id >< g) >>> first f  -- 交換
first f >>> arr fst = arr fst >>> f                    -- 単位
first (first f) >>> arr assoc = arr assoc first f      -- 結合
```

但し、`assoc`は

```haskell
assoc :: ((a, b), c) -> (a, (b, c))
assoc ~(~(a, b), c)) = (a, (b, c))
```

であり、ペアの構成を変更するものである。


以上の公理は直感的に分かるだろう。拡張は純粋な関数を`id`との積を持つ計算に拡張している。関手はFunctorの`(a -> b) -> f a -> f b`と同様であることがわかるだろう。これは`first`は`f`と`g`の合成の関係を保存する必要があることを表す。交換は、`arr (id >< g)`は`second g`であるので、`first f`と`second g`が交換可能であることを示している。結合は複数回に渡る`first`の適用を`assoc`を用いて一つの`first`に潰すことができることを保証する。

以上を踏まえて、計算の構造を表現する型クラスをCategoryを踏まえて作ってみよう。

```haskell
class Arrow a where
    arr :: (b -> c) -> a b c
    (>>>) :: a b c -> a c d -> a b d
    first :: a b c -> a (b, d) (c, d)
```

前述したとおり、`second`と`(***)`は`first`より導出できるので必要ない。
また、`idA`も不要である。というのも、`arr id`から直ちに導出できるからである。

これがいわゆるArrowである。

これらに加えて便利な関数として、計算に適用する前に入力を複製する`(&&&)`も存在する。

```haskell
(&&&) :: Arrow a => a b c -> a b c' -> a b (c, c')
f &&& g = arr dup (f >>> g)
    where dup b = (b, b)
```

CategoryはControl.Categoryに、ArrowはControl.Arrowに実装されている。
Arrow型クラスのインスタンスになるためには、Categoryのインスタンスになり、`arr`と`first`あるいは`***`を実装するだけで良い。

# Arrowでaddを抽象化してみる

最初に紹介した4つの計算をArrowのインスタンスにしてみよう。
型シノニムであると型クラスのインスタンスにはできないので、`newtype`する。

```haskell
newtype State s a b = ST ((s, a) -> (s, b))
newtype NonDet a b = ND (a -> [b])
newtype MapTrans a b c = MT ((a -> b) -> (a -> c))
```

## 状態変換子

状態における純粋な関数は、状態`s`には触れない。

```haskell
instance Arrow (State s) where
    arr f = ST (id >< f)
    ST f >>> ST g = ST (g . f)
    first (ST f) = ST (assoc . (f >< id) . unassoc
```

なお、`unassoc`はassoc`の逆変換

```haskell
unassoc :: (a, (b, c)) -> ((a, b), c)
unassoc ~(a, ~(b, c)) = ((a, b), c)
```

である。

## 非決定性

非決定性における純粋な関数は、一つの要素の計算である。

```haskell
instance Arrow NonDet where
    arr f = ND (\b -> f[b])
    ND f >>> ND g = ND (\b -> [d | c <- f b, d <- g c])
    first (ND f) = ND (\(b, d) -> [(c, d) | c <- f b])
```

## 写像変換子

純粋な写像変換子はただ関数を適用するだけである。

```haskell
instance Arrow (MapTrans s) where
    arr f = MT (f .)
    MT f >>> MT g = MT (g . f)
    first (MT f) = MT (zipMap . (f >< id) . unzipMap)

zipMap :: (s -> a, s -> b) -> (s -> (a, b))
zipMap h s = (fst h s, snd h s)

unzipMap :: (s -> (a, b)) -> (s -> a, s -> b)
unzipMap h = (fst . h, snd . h)
```

## 単純オートマン

純粋なオートマンは自らの状態を変えないものである。

```haskell
instance Arrow Auto where
    arr f = A (\b -> (f b, arr f))
    A f >>> g f = A (\b -> let (c, f') = f b
                               (d, g') = g c
                           in (d, f' >>> g')
    first (A f) = A (\(b, d) -> let (c, f') = f b
                                in ((c, d), first f')
```

## add

これらを用いて汎用的な`add`を書くことができる。

```haskell
add :: Arrow a => a b Int -> a b Int -> a b Int
add f g = f &&& g >>> arr (uncurry (+))
```

# 色々なArrowの派生

Arrowは抽象度が高すぎるので、もう少し制限したものが使われることが多い。
ここではそういったArrowのサブクラスについて紹介する。

## モナド(ArrowApply)

Haskellerであれば、タプルをみるとカリー化できるのではないかと考えるだろう。
実際にはArrowのインスタンスすべてがカリー化できるわけではないが、できるものもある。

```math
a\, (b,\, c)\, d \simeq b \rightarrow a\, c\, d
```

上記のカリー化同型に対して、右から左の関数が自明に存在する。

```haskell
curryA :: Arrow a => a (b, c) d -> b -> a c d
curryA f b = mkPair b >>> f
mkPair :: Arrow a => b -> a c (b, c)
mkPair b = arr (\c -> (b, c))
```

それでは、左から右の関数も存在するだろうか。
それは`a b d`を以下のように変換するものである。

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

上記のappが以下の公理を満たすようなArrowを特にArrowApplyという。

```haskell
arr ((>>> h) >< id) >>> app = app >>> h  -- 合成
arr (mkPair >< id) >>> app = arr id     -- 簡約
mkPair f >>> app f                       -- 外延性
```

純粋な関数はこれの自明なインスタンスである。

```haskell
instance ArrowApply (->) where
    app ~(f, c) = f c
```

ArrowApplyのインスタンスであるのは他に、StateとNonDetである。MapTransとAutoはこれのインスタンスではない。

上記のカリー化同型性があれば、`c = ()`のときに、

```math
a\, (b,\, ())\, d  \simeq a\, b\, d \simeq b \rightarrow a\, ()\, d
```

であり、これを満たすArrowは `b -> m d`という形を持つことになる。この`m`はいわゆるモナドである。
こういった形式のArrowを特にKleisli Arrowと呼び、カリー化同型性を満たすことが知られている。
早い話が、ArrowApplyはMonadと等価である。Monadの方が使い慣れているし、Monadを使った関数も多いので、敷いてArrowApplyを使う必要性はないだろう。

モナドとArrowとの違いは、複数の入力を消費したり、入力とは独立な計算を表すことができる点にある。

## 条件分岐(ArrowChoice)

異なる入力に対して条件分岐するというのは、プログラムにおいて当たり前に存在する。これは直接入力の値を参照するため、Arrowよりも強い制約が必要になるが、ArrowApplyよりかは抽象度が高い。まず直和型を考えてみよう。

```haskell
data Either a b = Left a | Right b
```

積のときと同様に考えると、この直和に対応する変換は次のように考えられる。

```haskell
(+++) :: a b c -> a b' c' -> a (Either b b') (Either c c')
left :: a b c -> a (Either b d) (Either c d)
right :: a b c -> a (Either d b) (Either d c)
```

`right`と`(+++)`も積の時と同様に`left`から導出できる。

この`left`が満たすべき公理も積の時と同様に考えれば以下のようになる。

```haskell
left (arr f) = arr (f +++ id)                          -- 拡張
left (f >>> g) = left f >>> left g                     -- 関手
left f >>> arr (id +++ g) = arr (id +++ g) >>> left f  -- 交換
left f >>> arr fst = arr fst >>> f                     -- 単位
left (left f) >>> arr assocsum = arr assocsum left f   -- 結合
```

なお、`assocsum`は

```haskell
assocsum :: Either Either (a, b) c -> Either a Either (b, c)
assocsum (Left (Left a)) = Left a
assocsum (Left (Right b)) = Right (Left b)
assocsum (Right c) = Right (Right c)
```

である。

よってこの直和を導入し、条件分岐をもつArrowのサブクラスは次のようになる。

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

このArrowChoiceは積に加えて和も定義されているので、それらの関係を表す公理も導入する必要があるだろう。`first`と`left`は以下の公理も満たす必要がある。

```haskell
first (left f) >>> arr distr = arr distr >>> left (first f)  -- 分配
```

なお、`distr`は

```haskell
distr :: (Either a b, c) -> Either (a, c) (b, c)
distr (Left a, c) = Left (a, c)
distr (Right b, c) = Right (b, c)
```

この`distr`は純粋な関数の世界の積と和の分配の関係を表している。
イメージとしては四則演算の分配法則とそう違わないと考えていい。
Eitherが和でタプルが積であることを考えて四則演算に翻訳すれば、`distr`は`(a + b) * c -> a * c + b * c`を表している。

積のときの`(***)`に対応するのが`(+++)`, `(&&&)`に対応するものとして、`(|||)`を導入する。

```haskell
(+++) :: ArrowChoice a => a b c -> a b' c' -> a (Either b b') (Either c c')
(|||) :: ArrowChoice a => 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のインスタンスになる。また、ArrowApplyのインスタンスであったState, NonDetは当然ながら、そうではなかったAutoもApplyChoiceのインスタンスである。これはArrowApplyよりも抽象度が高く、Arrowよりも抽象度が低いことを示している。

```haskell
instance ArrowChoice Auto where
    left (A f) = A lf
     where lf (Left b) = let (C, f') = f b
                         in (Left c, left f')
           lf (Right d) = (Right d, left (A f))
```

これはLeft側の入力のみがオートマンに消費され、それ以外は複製されることを示している。


## フィードバック(Arrowloop)

制御工学でやるような出力の値を入力に用いるフィードバックもArrowで表すことができる。

通常の関数であれば以下の`trace`関数を使えば良い。

```haskell
trace :: ((b, d) -> (c, d)) -> b -> c
trace f b = let (c, d) = f (b, d) in c
```

この関数は出力の二つ目の要素`d`が入力にフィードバックされている。

それではArrowを使ってこの`trace`関数を一般化しよう。

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

このフィードバックは値のみであり、計算自体は１回である。
これを踏まえると`loop`の公理は次のようになる。

```haskell
loop (arr f) = arr (trace f)                                       -- 拡張
loop (first h >>> f) = h >>> loop f                                -- 左結合
loop (f >>> first h) = loop f >>> h                                -- 右結合
loop (f >>> pure (id >< k)) = loop (pure (id >< k) >>> f)          -- 滑り込み
loop (loop f) = loop (pure unassoc >>> f pure assoc)               -- 消失
second (loop f) = loop (pure assoc >>> second f >>> pure unassoc)  -- 重合
```

例によって純粋な関数はこれのインスタンスである。

```haskell
instance ArrowLoop (->) where
    loop = trace
```

状態変換子をArrowLoopのインスタンスにすると、出力をフィードバックしつつ、１度だけ状態を操作できる。

```haskell
instance ArrowLoop (State s) where
    loop (ST f) = ST (trace (unassoc . f . assoc))
```

写像変換子も同様にArrowLoopのインスタンスにできる。これも出力をフィードバックしつつ一度だけ写像変換を行う。

```haskell
instance ArrowLoop (MapTrans s) where
    loop (MT f) = MT (trace (unzipMap . f. zipMap))
```

状態変換子のArrowLoopの定義とよく似ている。

オートマンは出力の一部をフィードバックするのに使える。

```haskell
instance ArrowLoop Auto where
    loop (A f) = A (\b -> let ~(c, d), f' = f (b, d)
                          in (c, loop f'))
```


以上が基本的なArrowのサブクラスである。
Arrowの基礎がわかっていれば自分で拡張することもできるだろう。(する意味あるかは微妙)

# Arrow記法

今までポイントフリースタイルでArrowを使ってきたが、これはMonadをdo記法なしで扱っているのと同じである。GHCでは言語拡張としてArrow記法をサポートしている。

```haskell
{-# LANGUAGE Arrows #-}
```

で導入できる。

## 文法

Arrow記法の文法は以下のとおりである。

```haskell
exp  = ...
     | proc pat -> cmd
cmd  = exp -< exp
     | do {stmt; ... stmt; cmd}
stmt = pat <- cmd
     | cmd
     | rec {stmt; ... stmt}
```

`proc`はArrowを伴う計算のラムダ式のようなものである。通常のラムダ式と違い、引数は必ず一つである。
`proc`は必ずコマンド`cmd`を返す。
コマンドはArrowを入力に適用する`-<`かdo記法になる。
do記法内の文`stmt`は変数の代入か、コマンドである。
コマンドは出力値の何らかの効果を持つが、文としてのコマンドは出力が捨てられる。
これはちょうどMonadでいう`>>`に似ている。
`rec`は再帰的な定義を用いる場合に使う。
これを使う際は当然であるがArrowLoopのインスタンスでなければならない。
ArrowChoiceのインスタンスであれば、上記のコマンドに加えて、値によって条件分岐を行う`if式やcase式が使えるようになる。

最終的な出力結果は`returnA -< n`の様にしてやれば得られる


# 使ってみる

試しに有名な例題である同期回路をArrowを使って表現してみる。

下のようなリセット可能なカウンタ回路を作ってみよう。

```
              reset
                |
               \|/         output
const 0 ------> IF ---------------->
               /|\           |
           next |           +1
                |__DERAY 0___|
```

このカウンタ回路は、論理値を入力として受け取り、最後に入力がTureになったときからのクロックの数をカウントするものである。
これを実現するために上記の回路では出力をインクリメントしたあと１クロック遅延させてから入力にフィードバックしている。
カウンタの初期値は引数で与えられたものとしている。(ここでは0)

フィードバックしているのでこのArrowは当然ArrowLoopのサブクラスになる。
このArrowの計算は遅延とフィードバックである。というのもIFと+1はどちらも純粋な関数だからである。

よってこのArrowは以下のように定義できる。

```haskell
class ArrowLoop a => ArrowCircuit a where
    delay :: b -> a b b
```

上記の図をそのままArrow記法で記述すると次のようになる。

```haskell
counter :: ArrowCircuit a => a Bool Int
counter = proc reset -> do
            rec output <- returnA -< if reset then 0 else next
                next <- delay 0 -< output + 1
            returnA -< output
```

全体の入力は`reset`である
do記法内ではフィードバックを行うので、`rec`によって再帰的な定義を行っている。
回路の値を`output`と`next`に分けている。このArrowの出力である`output`は恒等Arrowである`returnA`に入力することで、遅延は`delay 0`を実行することで実現している。

図がそのままArrow記法に対応しており、非常に簡単にArrowが扱えることがわかる。

後はArrowCircuitのインスタンスを作れば良い。単純オートマンをArrowCircuitのインスタンスにすれば、既にArrowLoopのインスタンスが存在するので楽に`counter`を実現できる。

```haskell
instance ArrowCircuit Auto where
    delay b = A (\b' -> (b, b'))
```

この回路のシミュレートは、これに入力のリストを与えることである。

```haskell
runAuto :: Auto b c -> [b] -> [c]
runAuto (A f) [] = []
runAuto (A f) (b : bs) = let (c, f') = f b in (c : runAuto f' bs)
```

# 余談

最後の方力尽きたて雑になってしまったので土日にでも加筆修正します……
非常にガバガバな解説なのでツッコミなどはお気軽にTwitter(@Lugendre)かコメントまで

# 参考文献

* [関数プログラミングの楽しみ](http://amzn.asia/9fPjLyg) 
  - これ読んどけばArrowわかるっていうくらい良書。最後の例題はここの引用。
* [Arrow notation](https://downloads.haskell.org/~ghc/7.8.4/docs/html/users_guide/arrow-notation.html)
  - Arrow記法に関する色々が載っているGHCの公式ドキュメント
* [Contorl.Arrow](https://hackage.haskell.org/package/base-4.10.1.0/docs/Control-Arrow.html)
  - HaskellにおけるArrowの実装はここ
* "Generalising Monads to Arrows", by John Hughes, Science of Computer Programming 37, pp67-111, May 2000.
  - 元論文
* "A New Notation for Arrows", by Ross Paterson, in ICFP 2001, Firenze, Italy, pp229-240.
  - returnAやloopの原典