アローはモナドの一般化であり、John Hughesによって導入された。詳細については、以下のものを見よ。
“Generalising Monads to Arrows”, John Hughes, in Science of Computer Programming 37, pp67–111, May 2000。アローを導入した論文である。平易な入門であり、動機付けとしてプログラミングの例が使われている。
“A New Notation for Arrows”, Ross Paterson, in ICFP, Sep 2001。 ここで記述されている記法を導入した。
“Arrows and Computation”, Ross Paterson, in The Fun of Programming, Palgrave, 2003.
“Programming with Arrows”, John Hughes, in 5th International Summer School on Advanced Functional Programming, Lecture Notes in Computer Science vol. 3622, Springer, 2004。 この論文にもこの記法への入門が含まれており、実際的な例もついている。
“Type and Translation Rules for Arrow Notation in GHC”, Ross Paterson and Simon Peyton Jones, September 16, 2004. 形式的な規則を簡潔に列挙したもの(ソースコード中のコメントから抽出された)。
http://www.haskell.org/arrows/
にアローのウェブページがある。
-XArrows
フラグが与えられると、GHCは二番目の論文に記述されているアロー記法をサポートする。この記法は、Control.Arrow
モジュールのコンビネータを使って通常のHaskellに翻訳される。以下に示すのは、この記法の短い紹介である。Hughesの論文を読まないとあまり意味が分からないだろう。
この拡張によって、アローを定義するための新しい種類の式が追加される。
exp
10 ::= ... | procapat
->cmd
ここで、proc
は新しいキーワードである。パターン中の変数はproc
式の本体において束縛されている。本体は、コマンドと呼ばれる、新しい種類のものである。コマンドの構文は以下のとおりである。
cmd
::=exp
10 -<exp
|exp
10 -<<exp
|cmd
0
加えて、cmd
0からcmd
9までが、式の場合と同じように、中置演算子を使って定義される。
cmd
10 ::= \apat
...apat
->cmd
| letdecls
incmd
| ifexp
thencmd
elsecmd
| caseexp
of {calts
} | do {cstmt
; ...cstmt
;cmd
} |fcmd
fcmd
::=fcmd
aexp
| (cmd
) | (|aexp
cmd
...cmd
|)cstmt
::= letdecls
|pat
<-cmd
| rec {cstmt
; ...cstmt
[;] } |cmd
ここで、calts
はalts
と同様だが、本体が式ではなくコマンドだという点が異なる。
コマンドは値を生み出すが、(モナドな計算と同じく)複数の値を生み出すこともあるし、零個のこともあるし、同時に別のことを行うこともある。大部分において、モナド記法に親しんでいればコマンドを使う上での良い助けになる。ただし、式(モナドなものも含めて)の値は含まれる変数の値によって決定されるのに対し、コマンドでは必ずしもそうではない。
次に示すのは、この新しい記法の簡単な例である。
proc x -> f -< x+1
これを、手続きまたはアロー抽象と呼ぶ。ラムダ式の場合と同様、変数x
はproc
式の内部で束縛される新しい変数である。この変数はアローへの入力を参照する。上の例で、-<
は識別子ではなく、新しい予約シンボルであり、アロー型の式とそのアローに食わせる式とからコマンドを構築するのに使う。(見た目が変だが、これについてはあとで納得できるだろう)。これはアローの適用に相当するものだと考えることもできる。上の例は次のHaskellの式に等しい。
arr (\ x -> x+1) >>> f
これは、-<
の左の式に束縛変数x
が現れていたらおかしなことになる。一般に、-<
の左側の式には局所変数(現在のアロー抽象で束縛された変数)が現れてはならない。このような場合のために、-<<
という変種があり、次のように使える。
proc x -> f x -<< x+1
これは以下のものと同じである。
arr (\ x -> (f x, x+1)) >>> app
よってこの場合のアローはArrowApply
クラスに属していなければならない。このようなアローはモナドと同等なので、モナドとして定式化した方が便利かも知れない。
コマンドはdo
記法の形をとることもある。例えば次のように書くことができる。
proc x -> do y <- f -< x+1 g -< 2*y let z = x+y t <- h -< x*z returnA -< t+z
これは通常のdo
記法と大体同じように読むことができる。ただし、モナドな式の代わりにコマンドが使われている。最初の行では、x+1
の値がアローf
に入力として送られ、出力がy
に対して照合される。次の行では、出力は捨てられている。returnA
というアローは、Control.Arrow
モジュールで、arr id
として定義されている。上の例は次のものの略記として扱われる。
arr (\ x -> (x, x)) >>> first (arr (\ x -> x+1) >>> f) >>> arr (\ (y, x) -> (y, (x, y))) >>> first (arr (\ y -> 2*y) >>> g) >>> arr snd >>> arr (\ (x, y) -> let z = x+y in ((x, z), z)) >>> first (arr (\ (x, z) -> x*z) >>> h) >>> arr (\ (t, z) -> t+z) >>> returnA
それ以降使われない変数は射影で捨てられていることに注意。これにControl.Arrow
で定義されている書き換え規則(7.21. 書き換え規則 を見よ)を使って単純化を施すと、以下のように簡約される。
arr (\ x -> (x+1, x)) >>> first f >>> arr (\ (y, x) -> (2*y, (x, y))) >>> first g >>> arr (\ (_, (x, y)) -> let z = x+y in (x*z, z)) >>> first h >>> arr (\ (t, z) -> t+z)
手で書くなら最初からこう書いたであろう。アロー記法を使えば、GHCがあなたの代わりにこれらの変数のタプルたちを管理してくれる。
なお、上の変換では、let
束縛された変数(たとえばz
)が単相的でなければならないように見えるが、実際の変換で生成されるのはcoreなので、変数は多相的であり得る。
相互再帰的な束縛を使うこともできる。これには、rec
という新しいキーワードを使う。以下のようになる。
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
このような形式は、変換すると、loop
コンビネータを使ったものになるので、その場合のアローはArrowLoop
クラスに属していなければならない。
前の例では、アローへの入力を構築するために条件式を使った。場合によっては、以下のように、条件によって異なるコマンドを実行したいことがある。
proc (x,y) -> if f x y then g -< x+1 else h -< y+2
これは次のように変換される。
arr (\ (x,y) -> if f x y then Left x else Right y) >>> (arr (\x -> x+1) >>> g) ||| (arr (\y -> y+2) >>> h)
変換結果で|||
が使われているので、この場合のアローはArrowChoice
クラスに属していなければならない。
以下のようなcase
コマンドもある。
case input of [] -> f -< () [x] -> g -< x+1 x1:x2:xs -> do y <- h -< (x1, x2) ys <- k -< xs returnA -< y:ys
構文はcase
式と同じであるが、選択肢の本体が式でなくコマンドである点が異なる。変換はif
で行われるものに似ている。
既に見たように、アロー記法には、逐次実行、値再帰、および条件分岐について、式のものを手本とした構文要素が提供されている。しかし、適切なコンビネータ(これはHaskellで普通に定義できる)があれば、それを、既存のコマンドから新しいコマンドをつくり出すのに使うこともできる。基本的な考え方としては、コマンドを、環境から値へのアローとみなすのである。環境は、コマンド中の自由な局所変数に値を割り当てる。これにより、アローからアローをつくり出すコンビネータは、コマンドからコマンドを構築するのにも使える。例えば、ArrowPlus
クラスには次のコンビネータがある。
ArrowPlus a => (<+>) :: a b c -> a b c -> a b c
よって、これを使ってコマンドを組み立てることができる。
expr' = proc x -> do returnA -< x <+> do symbol Plus -< () y <- term -< () expr' -< x + y <+> do symbol Minus -< () y <- term -< () expr' -< x - y
(最初の行のdo
は、最初の<+> ...
が、直前の行の式の一部だとみなされるのを防ぐために必要である)。これは以下のものと同等である。
expr' = (proc x -> returnA -< x) <+> (proc x -> do symbol Plus -< () y <- term -< () expr' -< x + y) <+> (proc x -> do symbol Minus -< () y <- term -< () expr' -< x - y)
ここでは、実は<+>
を以下の特殊化された型で使っている。
ArrowPlus a => (<+>) :: a (e,()) c -> a (e,()) c -> a (e,()) c
この演算子がe
(そのコマンドへの環境入力。必然的にそのサブコマンドへの環境入力にもなる)について多相的であって、少なくとも正格なk
については以下の自然性を満たす、ということが本質的に重要である。
arr (first k) >>> (f <+> g) = (arr (first k) >>> f) <+> (arr (first k) >>> g)
(seq
を使っていないなら自動的にこうなるはずである)。これにより、サブコマンドが見る環境がコマンド全体の環境と同じだということ、および変換において環境のうちの不要な部分を捨てても安全だということが保証される。(入力の対の第二要素は、次の節で述べるように、無名の入力値を持つことができる。)また、この演算子は、現在のアロー抽象の中で定義された変数を使っていてはならない。
次のように自分で演算子を定義し、同様の方法で使うこともできる。
untilA :: ArrowChoice a => a (e,s) () -> a (e,s) Bool -> a (e,s) () untilA body cond = proc x -> b <- cond -< x if b then returnA -< () else do body -< x untilA body cond -< x
もちろん、この中置記法の構文は二項演算子についてしかうまく働かない。特別な括弧を使った、より一般的な構文が存在する。
proc x -> do y <- f -< x+1 (|untilA (increment -< x+y) (within 0.5 -< x)|)
演算子によっては、サブコマンドに追加の引数を渡す必要がある。例えば、例外を扱えるアローにおいて、例外ハンドラを付加する演算子では、発生した例外をハンドラに渡したいと思うだろう。このような演算子は次のような型を持っていると考えられる。
handleA :: ... => a (e,s) c -> a (e,(Ex,s)) c -> a (e,s) c
ここで、Ex
は扱われる例外の型である。このとき、次のようなコマンドを書くことで、これをアロー記法中で使うことができる。
body `handleA` \ ex -> handler
意図は、コマンドbody
が例外を発生させたら、変数ex
がその例外の値に束縛され、コマンドhandler
(通常ex
を参照する)に進入する、というものである。この構文は関数のラムダに似ているが、ここで扱われているのはコマンドであって、やっていることが異なる。コマンドが表すアローの入力は、コマンド中の自由な局所変数の値に加えて、無名の値のスタックから成る。ここまでの例ではこのスタックについては何も仮定しなかった。handleA
の第二引数では、ハンドラに与えられたスタックに例外の値を追加している。コマンド用のラムダはこの値に名前を与えているに過ぎない。
より具体的にいうと、コマンドへの入力は、環境とスタックの対からなる。スタック中のそれぞれの値は、スタックの残りの部分との対になっており、空スタックは()
である。handleA
のような、サブコマンドに追加の入力を渡す演算子をこの記法で使えるようにするには、それらの追加入力の値をこのようにしてスタックに置けば良い。 さらに正確に言うと、演算子のそれぞれの引数(および結果)の型は以下の形をしているべきである。
a (e, (t1, ... (tn, ())...)) t
ここで、e
は(環境を表す)多相変数であり、ti
はスタック中の値の型であり、t1
が「先頭」である。多相変数e
はa
、ti
、t
に現れてはならない。一方、関係するアローが同じである必要はない。適切な演算子の例をもう少し示す。
bracketA :: ... => a (e,s) b -> a (e,(b,s)) c -> a (e,(c,s)) d -> a (e,s) d runReader :: ... => a (e,s) c -> a' (e,(State,s)) c runState :: ... => a (e,s) c -> a' (e,(State,s)) (c,State)
後ろ二者で作られたコマンドが必要とする追加の引数は、そのコマンドを通常の式に適用することで与えることができる。次のように。
proc x -> do s <- ... (|runReader (do { ... })|) s
これは、runReader
を使って作られたコマンドの入力のスタックにs
を加えている。
コマンド版のラムダ抽象と適用は式におけるそれに似ている。特に、β規則とη規則がコマンドの同等性を記述する。これらの三つの機能(演算子、ラムダ抽象、適用)がこの記法の核である。他のものは全てこれらを使って(不格好になるだろうが)構築することができる。例えば、次のように定義することによってdo
記法をシミュレートできる。
bind :: Arrow a => a (e,s) b -> a (e,(b,s)) c -> a (e,s) c u `bind` f = returnA &&& u >>> f bind_ :: Arrow a => a (e,s) b -> a (e,s) c -> a (e,s) c u `bind_` f = u `bind` (arr fst >>> f)
次のように定義することでif
をシミュレートできる。
cond :: ArrowChoice a => a (e,s) b -> a (e,s) b -> a (e,(Bool,s)) b cond f g = arr (\ (e,(b,s)) -> if b then Left (e,s) else Right (e,s)) >>> f ||| g
一種類のアロー適用(アロー尾部)に二通りの変換を用意する代わりに、実装では二種類、すなわち「-<
」(一階)と「-<<
」(高階)が提供されている。
ユーザ定義の演算子を明示するのに、form
という新しいキーワードではなく、バナナ括弧を使っている。
論文および以前の実装では、スタック中の値は環境と対にされ、その右側に置かれていた。今ではこれらは別々の引数である。
アロー記法を直接実装しているのはGHCだけであるが、アロー記法をHaskell 98に変換することで別のHaskellシステムでも使える前処理器(arrows web pageから入手可能)もある。それでも、アローを使ったプログラムをGHCで検査したいと思うかもしれない。前処理器の出力から型エラーを追跡するのは簡単ではないからである。モジュールを、GHCとこの前処理器の両方で使えるようにする場合、いくつか余分な制約が科せられる。
モジュールはControl.Arrow
をインポートしなければならない。
前処理器は他のHaskell拡張に対応していないので、そういうものは別のモジュールに置かなければならない。
前処理器の出力はHaskell(Coreではなく)なので、let
束縛された変数は単相的になる。