拡張可能作用 ― モナド変換子に取って代わるもの 2 - shiatsumat/fp-papers GitHub Wiki

まず、いくつかの例を使って、拡張可能作用ライブラリの感じを掴んでもらって、使い方を実証しようと思う。（完全なコード Eff.hs はこの論文に付属している。）このライブラリは [§3.4](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-4) で説明する非常に小さいコアの上に実装されていて、すべての Haskell プログラマにとって MTL [[24](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference24), Chap.18] のように見えるように設計されている。この MTL に似たインターフェースは[図1](拡張可能作用 ― モナド変換子に取って代わるもの 2#fig1)に示されている。二つの特に興味深い点は、(i) すべての作用を持つ計算がモナド Eff r で表されていて、かつ (ii) 型引数 r が Typeable でなければならない要素からなった独立の作用のオープンな和 (open union) である、ということである。この r は、直感的には計算されるかもしれない作用の集合であると考えることもできる。後で作用はリクエスト (request) によって表されているということを見るが、だからこそ r という名前なのだ。

図1. 拡張可能作用ライブラリのインターフェース

instance Monad (Eff r)

-- 純粋な計算
data Void
run :: Eff Void w -> w

-- 読取（あるいは環境）作用
type Reader e
ask       :: (Typeable e, Member (Reader e) r) => Eff r e
local     :: (Typeable e, Member (Reader e) r) =>
             (e -> e) -> Eff r w -> Eff r w
runReader :: Typeable e =>
             Eff (Reader e :> r) w -> e -> Eff r w

-- 例外
type Exc e
throwError :: (Typeable e, Member (Exc e) r) => e -> Eff r a
catchError :: (Typeable e, Member (Exc e) r) =>
              Eff r w -> (e -> Eff r w) -> Eff r w
runError   :: Typeable e =>
              Eff (Exc e :> r) w -> Eff r (Either e w)

-- 状態
type State s
get      :: (Typeable s, Member (State s) r) => Eff r s
put      :: (Typeable s, Member (State s) r) => s -> Eff r ()
runState :: Typeable s =>
            Eff (State s :> r) w -> s -> Eff r (w,s)

-- 非決定論
type Choose
choose     :: Member Choose r => [w] -> Eff r w
makeChoice :: Eff (Choose :> r) w -> Eff r [w]

-- トレース
type Trace
trace    :: Member Trace r => String -> Eff r ()
runTrace :: Eff (Trace :> Void) w -> IO w

-- 組み込みの作用（IO など）
type Lift m
lift    :: (Typeable1 m, MemberU2 Lift (Lift m) r) =>
           m w -> Eff r w
runLift :: (Monad m, Typeable1 m) =>
           Eff (Lift m :> Void) w -> m w

作用 m がこのオープンな和 r の一部であるということを表すには、2つの基本的な方法がある。（註：なお、より進んだ MemberU2 t (t m) r のような方法もあるが、後でより詳しく説明する。）1つ目は、型定数 (Member m r) である――これは 作用 m が集合 r の要素であることを表している。2つ目は、和 r を作用 m と残りの作用の集合 r へと分解する明示的なパターン (m :> r') を使う方法である――これは {m} ∪ r' と似ている。Void は空集合 ∅ と見なすこともできる（つまり、(Eff Void a) 型の計算は純粋である）。対照的に、(Eff (Reader Int :> Reader Bool :> Void) a) は2つの環境――Int 型の環境と Bool 型の環境――にアクセスするかもしれない。

小さい例として、以下の計算 t1 について考えてほしい。（註：数値リテラルが多相的であることを思い出そう。型注釈は、いくつものあり得る Reader の層の中から、Reader Int の作用の層を特に要求しているということを表している。この型注釈は柔軟性を犠牲にすれば完全に避けることができる。[§4](拡張可能作用 ― モナド変換子に取って代わるもの 4#section4) を参照せよ。）

t1 :: Member (Reader Int) r => Eff r Int
t1 = do v <- ask
        return (v + 1 :: Int)

型注釈を付けなければ多相的になる数値定数に型注釈を与えることで、t1 に対して推論された型は 、t1 がおそらく Int を含む環境を操作した後に Int を返す、ということを表すようになる。r が少なくとも Reader Int の作用を含むという事実は、(Member (Reader Int) r) という制約で表現されている。Reader モナドからの演算 ask が環境に現在ある値を尋ね、t1 がそれをインクリメントした値を返している。

runReader t1 (10 :: Int) などして環境に初期値を設定することにより、t1 の計算を実行することができる。この式の推論される型は (Eff r Int) であり、それ以上の制約は無い。Reader Int の作用はハンドルされているので、オープンな和から「取り除かれて」いるのだ。この場合は、残りの作用は無く、純粋な計算を run してただの Int を生み出すことができる。対照的に、run t1 は型エラーを起こす。

t1r = run $ runReader t1 (10 :: Int)
-- 11

t1rr' = run t1
-- No instance for (Member (Reader Int) Void)
-- arising from a use of 't1'

ゆえに型は、すべての作用が確実にハンドルされるようにする作用のシステムの一部なのである。

式のレベルにおいて、計算 t1 のコードは MTL ベースの実装と同じである。型のレベルにおいて、制約 (Member (Reader Int) r) はどちらかというと MonadReader の制約に似ている。実際、私たちは Eff r モナドに対して MonadReader インスタンスを定義することもできる。しかし、Eff r はより一般性がある。上述のように、r は Reader 作用をいくつでも持てるのだ。（註：しかし、MonadReader のバージョンは多相的な数値に対し、型注釈がより少なくて済む。議論については [§4](拡張可能作用 ― モナド変換子に取って代わるもの 4#section4) を参照。）

t2 :: (Member (Reader Int) r, Member (Reader Float) r) =>
      Eff r Float
t2 = do
 v1 <- ask
 v2 <- ask
 return $ fromIntegral (v1 + (1 :: Int)) + (v2 + (2 :: Float))

ask をするたびに、型によって（ここでは Int か Float）環境を探して値を取得する。t2 をそのままモナド変換子を使って書くことは出来ない。Reader 作用を2つ使っているので、モナド変換子は私たちに、順番を選んで明示的に lift を使うことを強制する。対称的に、t2 に対する推論された型注釈は、2つの Reader 作用の順序を何も指定しない。（註：型注釈における型クラス制約の順序は重要でない。）順序は計算が実行されるときに初めて決まる。

t2r = run $ runReader (runReader t2 (10 :: Int)) (20 :: Float)
-- 33.0

2つの runReader の現れを交換して、作用を逆順にすることもできる（この場合は結果は変わらない）。

例外などの制御作用 (control effect) があるときは、作用を操作する順番は重要になってくる。以下の計算 incr は MTL に似た演算 get と put を使って Int の状態をインクリメントする。tes1 はこの状態の操作を例外と組み合わせる。

incr :: Member (State Int) r => Eff r ()
incr = get >>= put . (+ (1 :: Int))

tes1 :: (Member (State Int) r, Member (Exc String) r) =>
        Eff r a
tes1 = incr >> throwError "exc"

tes1 に対する推論された型注釈は、2つの作用が特定の順番で「組み合わさって」いないということを示している――tes1 を実行 (run) するには State と Exc の作用の両者をハンドルしなければならないので、どちらを先にハンドルするか選ばなければならないのだ。先ほどの例とは違い、選択は重要である（型にそれは表れている）。

ter1 :: (Either String String, Int)
ter1 = run $ runState (runError tes1) (1 :: Int)
-- (Left "exc",2)

ter2 :: Either String (String, Int)
ter2 = run $ runError (runState tes1 (1 :: Int))
-- Left "exc"

例外が起こった時点で、ter1 が蓄積された状態を保持しているのに対し、ter2 はその状態を無視している――1つ目の意味論が従来の、多くの言語（Scheme, ML, Java など）にある「組み込みの」状態と例外のやりとりをモデル化しているのに対し、2つ目の意味論は例外が失敗した「トランザクション」を表し、状態が元の値に戻されることを要求している。

これは、複数の作用についての別の例である。作用のある関数 f をリストの各要素に適用し、デバッグ用のトレースをプリントする、高階関数である。

mapMdebug :: (Show a, Member Trace r) =>
             (a -> Eff r b) -> [a] -> Eff r [b]
mapMdebug f [] = return []
mapMdebug f (h:t) = do
 trace $ "mapMdebug: " ++ show h
 h' <- f h
 t' <- mapMdebug f t
 return (h':t')

add :: Monad m => m Int -> m Int -> m Int
add = liftM2 (+)

tMd = runTrace $ runReader (mapMdebug f [1..5]) (10 :: Int)
 where f x = ask `add` return x
-- mapMdebug: 1
-- mapMdebug: 2
-- mapMdebug: 3
-- mapMdebug: 4
-- mapMdebug: 5
-- [11,12,13,14,15]

推論された型は、Trace 作用が f が生成しうる任意の作用に付け足されることを表している。例 tMd では f を環境作用と共に用いている。ここに作用の合成可能性を見ることができる――2つの独立したコードの断片とその作用の型は、作用を両方辿るという文脈ですんなりと使うことができる。

私たちのフレームワークは既存のモナドライブラリ（ユーザーが作ったものでも IO などの組み込みのものでも構わない）と共に使うことができる。例えば、

tl1 :: (MemberU2 Lift (Lift IO) r, Member (Reader Int) r) =>
       Eff r ()
tl1 = ask >>= \(x::Int) -> lift . print $ (x + 1 :: Int)

は Reader と IO の作用を何らかの順番で組み合わせる。これは tl1 の推論された型を見ても明らかだろう。あるモナド m の作用はこのフレームワークでは (Lift m) と表記される。一般に任意のモナドを合成することは出来ないので、計算に対して Lift の作用は最大でも一つしかあってはならない。これは、lift の MemberU2 Lift (Lift m) r という制約を見ても分かる（[図1](拡張可能作用 ― モナド変換子に取って代わるもの 2#fig1) を参照）。ゆえに、先ほどの例のデバッグ関数 mapMdebug を Trace の代わりに (Lift IO) 作用を使って実装することもできた（mapMdebug の trace という部分を lift (print h) に変えるだけで良い）。新しい mapMdebug は以前と同様に、マッピング関数 f の作用を IO と組み合わせることで使える。

この簡単に記述されたフレームワークは、完全に拡張可能でもある。[図1](拡張可能作用 ― モナド変換子に取って代わるもの 2#fig1) のインターフェースはプログラマが自由に拡張できるユーザーライブラリとして実装されている。私たちは、このアプローチを詳しく説明して、モナド変換子の限界と比較した後で、より進んだ例について調べていく。