Arrowの話をしよう　(1)ArrowとArrow記法

Q: そんなタイトルで大丈夫か？
A: 大丈夫だ、問題ない。

Q: Arrowってなに？
A: あれは今から36万…いや、1万4千年前だったか…まぁいい、私にとってはつい昨日の出来事だが、君たちにとっては多分明日の出来事だ。彼には72通りの名前があるから、なんて呼べばいいのか…確か最初に会ったときは、Morphism…

...

こめんなさい…今のは真っ赤な嘘です…

http://www.haskell.org/arrows/
から引用：

Arrows are a new abstract view of computation, defined by John Hughes [Hug00]. They serve much the same purpose as monads -- providing a common structure for libraries -- but are more general.

その通り、実際Arrowとモナドの関係が近いと示す例は簡単に挙げられます：
add関数のモナド版：

addM :: Monad m => m Int -> m Int -> m Int
addM a b = do a' <- a
              b' <- b
              return (a' + b')

--output: Just 42
main = print $ addM (Just 10) (Just 32)

add関数のArrow版、GHCの拡張Arrow記法使用：

{-# LANGUAGE Arrows #-}

addA :: Arrow a => a b Int -> a b Int -> a b Int
addA a b = proc v -> do a' <- a -< v
                        b' <- b -< v
                        returnA -< (a' + b')

--output the same: Just 42
main = print $ runKleisli (addA (Kleisli (\_->Just 10)) (Kleisli (\_->Just 32))) "dummy"

さらに面白いのは：

main = -- 「ArrowMonad (Kleisli (\_->Just 10)」はモナド 
       return (addM (ArrowMonad (Kleisli (\_->Just 10))) (ArrowMonad (Kleisli (\_->Just 32)))) >>  
       -- 「Kleisli (\_->(ArrowMonad (Kleisli (\_->Just 10))))」 はArrow 
       return (addA (Kleisli (\_->(ArrowMonad (Kleisli (\_->Just 10))))) (Kleisli (\_->(ArrowMonad (Kleisli (\_->Just 32)))))) >>
       -- 「ArrowMonad (Kleisli (\_->(ArrowMonad (Kleisli (\_->Just 10)))))」はモナド 
       return (addM (ArrowMonad (Kleisli (\_->(ArrowMonad (Kleisli (\_->Just 10)))))) (ArrowMonad (Kleisli (\_->(ArrowMonad (Kleisli (\_->Just 32))))))) >>
       --  無限ループって怖くね？
       return ()

この関係が圏論の言葉で「随伴(adjunction)」と言います。すべてのArrowとモナドはこの関係を満たすわけではないので、上のはちょっと特殊な一例です。話しが少し脱線したので、最初に戻りましょう――じゃArrowってなに？答える前に、まずArrowの定義を見ましょう：

class Category a => Arrow a where
        -- | Lift a function to an arrow.
        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

最初に注目させたいのは「Category a => Arrow a」の部分、そう、ArrowはCategoryのサブクラス、その本質は圏です。って事は、Arrowまずは圏の法則(idとcomposition-association)を守なければなりません。

class Category cat where
        -- | the identity morphism
        id :: cat a a
        -- | morphism composition
        (.) :: cat b c -> cat a b -> cat a c

これからは主に一番単純なArrow(->)で説明します。Arrow(->)のobjectは普通の関数で、一番理解しやすいのではないかと思ってますから。

instance Category (->) where
        id = Prelude.id
        (.) = (Prelude..)

-- 下記圏の法則を満たす：
-- id . f = f = f . id
-- (f . g) . h = f . (g . h)

モナド則がモナドにとっては大事なことのように、圏の法則は(->)に限らず、全てのArrowにとって非常に重要なので、ぜひ覚えてください。
次はArrowのメンバー関数を見ましょう：arrとfirst以外にデフォルトの実装があり、Arrowを定義するに最小限の実装はarrとfirstの実装となります。まずはarr:

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

arrは普通関数をArrowのobjectに変換するメソードです。「a b c」のような形式はArrowのobjectの一般形式です。例えばArrow(->)のArrow形式は「(->) b c」と頭の中に変換するといい。注意してほしいのは「『a b c』は『b->c』の糖衣構文」のような思考方式に囚われないでください。(->)は非常に特殊なArrowなのでそう見えなくもないが、違います。確かにArrowのobjectは関数だが、必ずにも変換前の関数と一致するわけではありません（てか一致するケースが(->)だけ）。例えばArrow(Kleisli m)のobjectは「b->c」ではなく「b->m c」です：

newtype Kleisli m b c = Kleisli { runKleisli :: b -> m c }

arrの話しに戻ります。arrは普通関数をArrowのobjectに変換、或いはマッピングするってことは、arrは(圏論の意味で)functorです。なのでfunctorの法則を満たさなければならない：

arr Prelude.id = Category.id
arr (f . g) = arr f . arr g

これも圏の法則と同じ重要なのでぜひ覚えてください。因みに、Arrow(->)のarrは普通関数を自分自身へマッピングするfunctor: 「I -> I」です。ここまで来たら、「Arrowってなに?」の答えは自然に出てきたんでしょう：

モナドが $f:\hspace{10}a\to Fb$ のような関数を結合するための計算構造とするなら、
Arrowは $f:\hspace{10}Fa\to Gb$ のような関数を結合するための計算構造である。

これまでの説明で圏論的なArrowはもう完成されたが、実際使うにはいくつの足りないところがあります。例えば:

foo :: Arrow a => a b c -> a c d -> a b d
foo f g = f >>> g

のような形の関数だとfとgをは簡単に結合できるが(因みに「>>>」は「.」の逆順です。f >>> g = g . f)、冒頭のaddAのような形の関数はどうすればいいんだろう？出来ればモナドのbind演算子「>>=」みたいのがほしいな〜っと皆そう考えてるっしょ。もう最初からネタバレしたと思うが、答えは：出来ます。firstとその仲間はまさにその為の存在です。まず「>>=」の型定義を思い出しましょう：

(>>=) :: Monad m => m a -> (a -> m b) -> m b

もしArrowがbind関数があれば、パッと考えられるのは：

bind :: Arrow a => a b c -> ( (c -> d) -> a b d ) -> a b d

くらいだろう…まぁさておき、まずfirstとやらを見てみましょう：

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

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

first: 入力と出力はtupleの新しいArrowを返す。この新しいArrowの(fst 入力)と(fst 出力)は元のArrowと一緒、(snd 出力)は(id (snd 入力))である。
second: firstのミラーイメージ。
(***): 二つArrowを一つに統合する。
(&&&): 二つArrowの入力を一つにする。

使い道はともかく、tupleばかりなんで、上のbindの定義もtupleに合わせた方がいいでしょう…まぁ実際もそうだけどね。bindの定義：

bind :: Arrow a => a b c -> a (b,c) d -> a b d
u `bind` f = arr id &&& u >>> f

この関数さえあれば、だれもaddAなんか簡単に書けるのではないでしょうか：

addA a b = (arr (\v -> v) >>> a) `bind`
           ( 
             (arr (\(v, a') -> v) >>> b) `bind` 
              arr (\((v, a'), b') -> (a' + b'))
　　　　　 )

っておい、全然簡単じゃねぇし。
その通り、全然面倒くさいです。だから頭のいい人たちがArrowの専用記法を作りました：

proc p -> e1 -< e2 = arr (\p -> e2) >>> e1                   -- 1
proc p -> e1 -<< e2 = arr (\p -> (e1, e2)) >>> app           -- 2
proc p -> c1 `op` c2 = (proc p -> c1) `op` (proc p -> c2)    -- 3
proc p -> \p' -> c = proc (p, p') -> c                       -- 4

ついでにモナドのreturnをシミュレーションするためにreturnAも定義しました：

returnA :: Arrow a => a b b
returnA = arr id

というわけで、私たちのaddAもこれらの記法で直します：

addA a b = (arr (\v -> v) >>> a) `bind`
           ( 
             (arr (\(v, a') -> v) >>> b) `bind` 
              arr (\((v, a'), b') -> (a' + b'))
　　　　　 )

--------↓↓↓↓↓↓↓↓-----------

--ルール1
addA a b = ( proc v -> a -< v ) `bind`
           (
             (proc (v, a') -> b -< v ) `bind`
              proc ((v, a'), b') -> returnA -< (a' + b')
           )

--------↓↓↓↓↓↓↓↓-----------

--ルール4
--コンパイル通らない
addA a b = ( proc v -> a -< v ) `bind` 
           (
             (proc (v, a') -> b -< v ) `bind` 
              proc (v, a') -> \b' -> returnA -< (a' + b')
           )  

--------↓↓↓↓↓↓↓↓-----------

--ルール3
addA a b = ( proc v -> a -< v ) `bind` 
           ( proc (v, a') -> (b -< v) `bind` 
                             \b' -> returnA -< (a' + b') )

--------↓↓↓↓↓↓↓↓-----------

--ルール4
--コンパイル通らない
addA a b = ( proc v -> a -< v ) `bind` 
           ( proc v -> \a' -> (b -< v) `bind` 
                              \b' -> returnA -< (a' + b') )

--------↓↓↓↓↓↓↓↓-----------

--ルール3
--最終形態ではない、私はまだ1回の変身を残しています
addA a b = proc v -> (a -< v) `bind` \a' ->
                     (b -< v) `bind` \b' -> 
                     returnA -< (a' + b')

--------↓↓↓↓↓↓↓↓-----------

--Arrow do記法
addA a b = proc v -> do a' <- a -< v
                        b' <- b -< v
                        returnA -< (a' + b')

というわけですね。おわかりいただけただろうか？
(つづく？)

参考資料：

[Hug00] John Hughes, Generalising Monads to Arrows, in Science of Computer Programming 37, pp67-111, May 2000.
[Pat01] Ross Paterson, A New Notation for Arrows, in ICFP 2001, Firenze, Italy, pp229-240
http://www.haskell.org/ghc/docs/7.0.2/html/users_guide/arrow-notation.html