HaHaHa!(old)

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 
    |    |       |     |	      |    |       |     |	        |    |       |     |	      	   
     ~~~~         ~~~~~                ~~~~         ~~~~~                ~~~~         ~~~~~             
  • プログラムの外側の世界の変遷は↑の図の上半分にあらわれていて, w ⇒ w' ⇒ w''
  • プログラムの内側の値の変遷は↑の図の下半分にあらわれていて, 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 を作ってシミュレーションしてみる

あとで書いた.http://haskell.g.hatena.ne.jp/nobsun/20060908

酒井酒井2006/09/10 03:35些細かつ非本質的な点ですが、Actionの定義にはnewtypeを使った方が良いと思います。

nobsunnobsun2006/09/10 10:46newtypeの説明をどうしようか迷ったんです。で、安直にdataを使いました。でも思いなおして newtype にしました。