2006-09-07
■ HaskellのモナドIO
「Haskell : モナドはややこしい - lethevert is a programmer」ですか
「酒井さんのコメントの一言で終了！」と片づけてしまうには惜しい面白い問題なので少し考えてみました．
アクション
Haskellでは同じ有効範囲内(スコープ)の字面が同じ式は同じ値を指しています．つまり，参照透明性があるということです．
f :: a -> b
という関数を考えたとき，関数適用 f (x::a) :: b の値は x の値にのみ依存するということです．
式 f x を簡約してその値を求めることを「式の評価」といいます．評価順序は必要になる値の順序になります．値に対するデマンドドリブンというわけです．
さて，f が入出力を行う手続だとしたら f を引数に適用したときの値は，引数の値だけではなく，その時のプログラムの外側の世界に依存することになります．また，入出力を「実行」した後の世界は，「実行」前の世界とは別の世界になっているでしょう．この様子を Haskell のプログラムで表現すると(つまり世界の更に外側から見ると)，
f :: (a, World) -> (b, World)
となるでしょう．
f
_______
| |
(w :: World) --+---+---+--> (w' :: World)
| | |
| | |
| | |
(x :: a) --+---+---+--> (y :: b)
| |
~~~~~~~
手続 f をカリー化すると，
f :: a -> World -> (b, World)
になります．これは，
f :: a -> (World -> (b, World))
のことです．World -> (b, World) の部分は，「世界から，b型の値と新しい世界の対への手続」と読めます．この手続をアクションと呼ぶことにしましょう．プログラムの内側から見るとこのアクションは，b 型の値を生み出すものであり，外側から見ると，世界を変換するものに見えます．
ここで，a 型の値を生み出すアクションの型 Action a を定義しましょう．
newtype Action a = Act (World -> (a, World))
これを絵にすると
Action a
_______
| |
(w :: World) --+---+---+--> (w' :: World)
| | |
| | |
| | |
| `---+--> (x :: a)
| |
~~~~~~~
こんな感じでしょうか．このアクションを「走らせる(run)」すなわち，Action が保持する手続を世界に適用すると，新しい世界と a 型の値が得られます．アクションを使って，この世界を次の世界に変換することをアクションの「実行」と呼ぶことにしましょう．
アクションを順にならべる．
アクションを順に繋ぐ演算(>->)を考えましょう．
Action b
_______________________________
| Action a Action b |
| _____ _____ |
| | | | | |
w --+-+--+--+---> w' w'--+--+--+-+---> w'':: World
| | | | | | | |
| | | | >-> | | | |
| | | | | | | |
| | `--+---> x :: a | `--+-+---> y :: b
| | | | | |
| ~~~~~ ~~~~~ |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
この演算子は，左のアクションを世界 w で「走らせて」出来た世界 w'を，右のアクションに伝えるように，2つのアクションを合成します．つまり，合成されたアクションを，世界 w で「走らせる」と，左のアクションが先ず「走り」次に右のアクションが走って，最後に b 型の値 y と新しい世界 w'' が得られます．
(>->) :: Action a -> Action b -> Action b
(Act a) >-> (Act b) = Act (\ w -> let {(_,w') = a w; (y,w'') = b w'} in (y,w''))
この演算子で合成すると，左側のアクションを「走らせ」て得た a 型の値は捨てることになります．この演算子を一般化して，左のアクションを「走らせ」て得られた a 型の値を元にアクションを作って，これに左のアクションを「走らせ」て得られた新しい世界を伝えるように，アクション(Action a)とアクション生成関数(f :: a -> Action b)を合成する演算子(>=>)を考えてみましょう．
Action b
___________________________________________
| Action a Action b |
| _____ _____ |
| | | | | |
w --+-+--+--+---> w' w'--------------+--+--+-+---> w'':: World
| | | | | | | |
| | | | >=> ____ +--> | | | |
| | | | | f | | | | | |
| | `--+---> x :: a --+----+--+ | `--+-+---> y :: b
| | | | | | | |
| ~~~~~ ~~~~ ~~~~~ |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
すなわち，
(>=>) :: Action a -> (a -> Action b) -> Action b
(Act a) >=> f = Act (\ w -> let {(x,w') = a w; (y,w'') = f x w'} in (y,w''))
こちらを使うと (>->) は，
aa >-> ab = aa >=> \ _ -> ab
と定義できます．アクションの連鎖は，
Action a Action b Action c
_____ _____ _____
| | | | | |
w --+--+--+---> w w ---------------+--+--+---> w' w'----------------+--+--+---> w''
| | | | | | | | |
| | | >=> ____ +--> | | | >=> ____ +--> | | |
| | | | f | | | | | | g | | | | |
| `--+---> x :: a --+----+--+ | `--+---> y :: b --+----+--+ | `--+---> z :: c
| | | | | | | | | |
~~~~~ ~~~~ ~~~~~ ~~~~ ~~~~~
のように表現できます．ここでは，最初の Action a は世界には手を入れず，x :: a を生成するアクションになっています．このようなアクションを作りだす unit :: a -> Action a を定義しておきましょう．unit は f や g のようなアクションを生成する関数のうち，もっとも単純なものです．
unit :: a -> Action a unit x = Act (\ w -> (x,w))
この unit を入れて連鎖を描きなおすと
Action a Action b Action c
_____ _____ _____
| | | | | |
w ---------------+--+--+---> w w ---------------+--+--+---> w' w'---------------+--+--+---> w''
| | | | | | | | |
____ +--> | | | >=> ____ +--> | | | >=> ____ +--> | | |
|unit| | | | | | f | | | | | | g | | | | |
a --+----+--+ | `--+---> x :: a --+----+--+ | `--+---> y :: b --+----+--+ | `--+---> z :: c
| | | | | | | | | | | |
~~~~ ~~~~~ ~~~~ ~~~~~ ~~~~ ~~~~~
プログラムの「実行」というのは新しい世界を求めることです．そのために，アクションを「走らせる」わけです．
このように連結されたアクションは左から順に「走り」ます．すなわち，アクションの「実行」は左から順におこります．世界の変遷を表わすためにアクションを順に並べたので，アクションの実行は z::c の値を求めるための要求で駆動するのではなく，最終世界 w'' の値を求めるための要求駆動であることに注意してください．
Action は Monad だった
上で考えたアクションとアクションに関する基本演算 unit と 合成(>=>)との間には以下のような関係があります．
(1) 「unit x で作ったアクション」と「関数 f」を合成してできるアクション
≡
関数 f を x に適用してできるアクション
(2) 「アクション a」と「関数 unit」を合成してできるアクション
≡
アクション a
(3) 「「アクション a」と「関数 f」を合成したアクション」と「関数 g」を合成したアクション
≡
「アクション a」と「値 x から 「「アクション f x」と「関数 g」を合成したアクション」を生成する関数」を合成したアクション
つまり，
(1) unit x >=> f ≡ f x (2) a >=> unit ≡ a (3) (a >=> f) >=> g ≡ a >=> (\ x -> f x >>= g)
ということです．これはモナド則です．というわけで，Action, unit, (>=>) は Monad を形成できるわけです．
Action の世界を Haskell で書くと
ここまでを Haskell で書くと，
data World newtype Action a = Act (World -> (a, World)) run :: Action a -> World -> (a,World) run (Act a) w = a w exec :: Action a -> World -> World exec = (snd .) . run eval :: Action a -> World -> a eval = (fst .) . run (>=>) :: Action a -> (a -> Action b) -> Action b (Act a) >=> f = Act (\ w -> let (x,w') = a w in run (f x) w') unit :: a -> Action a unit x = Act (\ w -> (x,w)) (>->) :: Action a -> Action b -> Action b a >-> b = a >=> const b instance Monad Action where return = unit (>>=) = (>=>)
簡単な World を作ってシミュレーションしてみる
酒井2006/09/10 03:35些細かつ非本質的な点ですが、Actionの定義にはnewtypeを使った方が良いと思います。
nobsun2006/09/10 10:46newtypeの説明をどうしようか迷ったんです。で、安直にdataを使いました。でも思いなおして newtype にしました。
