bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

オペレーショナル・モナドを解剖する(2)

1.論理の世界から現実の世界

プルグラムは命令の並びであるが、プログラムとプログラムを接続したものも、またプログラムである。プログラムを命令の集まりとみなしている間は論理の世界で閉じているが、プログラムの並びをプログラムとみなすと、論理の世界からはみ出し、現実の世界に移行する。ここでは、移行のための準備をする。

命令が結果を返すようにした場合の状況を把握するために、ここでは、Cons sの命令を実行すると、そのリストの長さを戻り値としても返すこととする。このリストは長さ注釈つきリストなので、それ自身も長さの情報を有しているが、新たなリストができたとき、リストの長さを出力することにする。(ただし、Nilはリストの長さを返さないものとする。即ち、出力はないものとする。)

命令の戻り値は同じ型とは限らないので、命令の定義には代数的データ型を用いる。

data ListInstruction s n a where
  Nil   :: ListInstruction s n ()
  Cons  :: s -> ListInstruction s n Int

上の定義で、型引数sとnは、これまでと同じで、リストとその長さのデータ型を示す。型引数aは命令を出力したときの出力値のデータ型を示す。Nilの戻り値は( )でなし、Consの戻り値は整数である。

2.戻り値の束縛

命令が戻り値を持つと、プログラムも戻り値を持つことになる。最初の命令を(Cons s)でそれに続く残りの命令列をrestとすると、これは次のように表すことができる。

  a <- Cons s ; rest

最初をひっくり返すと、

  Cons s -> a ; rest

これはラムダ式を用いると次のように変形できる。

  Cons s ; \a -> rest

;を中置関数`Then`を用意して置き換えると次のようになる。

  Cons s `Then` \a -> rest

前の記事で出てきたexample1 = Cons 5 : Cons 3 : Cons 1 : [ ]は

  example1 = Cons 5 `Then` (\a -> Cons 3 `Then` (\b -> Cons 1 `Then` (\c -> Return))

となる。

これは次のようにも書ける。

  example1 = Cons 5 `Then` \a -> 
             Cons 3 `Then` \b -> 
             Cons 1 `Then` \c -> 
             Return

Thenはコンストラクタとして、Returnを除けば次のように表すことができる。

Then :: instr a -> (a -> Program instr b) -> Program instr b

また、空の命令[ ] に対応するReturnはコンストラクタとして、次のように表すことができる。

Return :: a -> Program instr a

このようにすることで、Returnは与えられた値を返すことができる。例えば、出力された長さの総和(あまり意味はない)を出力する場合には、次のようになる。

example1 = Cons 5 `Then` (\a -> Cons 3 `Then` (\b -> Cons 1 `Then` (\c -> Return(a + b + c))))interpret 

これにより、プログラムに終了時の自由度を与えることになる。(なお、上記のプログラムで、`Then`については結合律が成り立つので、計算の順序によらないことになる。従って、カッコを取り除いても同じである。)

そこで、プログラムの定義は次のように変更する。

data Program instr a where
  Then :: instr a -> (a -> Program instr b) -> Program instr b
  Return :: a -> Program instr a

リストを処理するプログラムは戻り値がついて次のようになる。

type ListProgram s n a = Program (ListInstruction s n) a

リストの定義は変わらず次の通りである。

data List s n = List {content :: [s], length' :: Int} deriving Show
displayList x = show (content x, length' x) ++ "\n"

3.命令の解釈:実行

命令の解釈・実行の部分は次のようになる。

interpret :: ListProgram s n a -> (List s n -> a)
interpret (Nil    `Then` is) _                                = interpret (is ()      ) List {content = [], length' = 0}
interpret (Cons x `Then` is) List {content = xs, length' = n} = interpret (is ((+1) n)) List {content = (x:xs), length' = ((+1) n)}
interpret (Return c        ) _                                = c

次を実行すると、所望の結果12を得ることができる。

example1 = Cons 5 `Then` (\a -> Cons 3 `Then` (\b -> Cons 1 `Then` (\c -> Return(a + b + c))))
main1 :: IO ()
main1 = (putStrLn . show) $ interpret example1 (List {content = [4,2], length' = 2})

プログラムはほぼ完ぺきに動いているので、論理の世界だけでもよさそうなのだが、人間はもっと欲望に満ちている。命令を並べたプログラムだけでなく、プログラムとプログラムとを結合した(前の記事では++を用いた)ものもプログラムとして扱えるようにしたい。そのためには、命令を接続している中置関数`Then`を拡張する必要がある。