Arrowを理解する

これはHaskell Advent Calendar その１ 8日目の記事です。

前日の記事は@nobsunさんのTree: 親子関係の付け替えでした。

対象者

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

Arrowとは

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

計算の構造を探る

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

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

状態変換

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

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

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

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で先に状態を消費することも可能である。

非決定性

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

type NonDet a b = a -> [b]

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

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

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

写像変換

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

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

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

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

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はそれぞれの値、時間において入力を評価し、その結果を足し合わせている。

単純オートマン

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

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

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

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関数を一般化する上でこれらの計算を合成している事がわかる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(***) :: a b c -> a b' c' -> a (b, b') (c, c')

である。(ここでは別物として><を(***)で置き換えている)

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

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

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

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

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のみを実装すれば良い。

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は以下の公理を満たす必要がある。

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は

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を踏まえて作ってみよう。

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である。

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

(&&&) :: 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する。

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には触れない。

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`の逆変換

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

である。

非決定性

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

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])

写像変換子

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

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)

単純オートマン

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

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を書くことができる。

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のインスタンスすべてがカリー化できるわけではないが、できるものもある。

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

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

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を以下のように変換するものである。

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

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

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

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

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

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

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

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よりかは抽象度が高い。まず直和型を考えてみよう。

data Either a b = Left a | Right b

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

(+++) :: 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が満たすべき公理も積の時と同様に考えれば以下のようになる。

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は

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のサブクラスは次のようになる。

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

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

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

なお、distrは

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を表している。

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

(+++) :: 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よりも抽象度が低いことを示している。

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関数を使えば良い。

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

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

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

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

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

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)  -- 重合

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

instance ArrowLoop (->) where
    loop = trace

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

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

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

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

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

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

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記法をサポートしている。

{-# LANGUAGE Arrows #-}

で導入できる。

文法

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

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は以下のように定義できる。

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

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

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を実現できる。

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

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

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)かコメントまで

参考文献

• 関数プログラミングの楽しみ
  • これ読んどけばArrowわかるっていうくらい良書。最後の例題はここの引用。
• Arrow notation
  • Arrow記法に関する色々が載っているGHCの公式ドキュメント
• Contorl.Arrow
  • 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の原典

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