bitterharvest’s diary

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

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

1.論理の世界

前回の記事で、米田の補題との関連を述べたが、オペレーショナル・モナドの命令の実行部分については詳しくは触れなかった。今回は、オペレーショナル・モナドの解釈・実行部分、プログラムではiterpretと記述、の部分について説明する。

例によって、長さ注釈つきのリストを用いて説明する。モナドを用いた現実の世界で話をすると複雑になるので、論理の世界で話を進め、これを現実の世界の話に移すこととする。

オペレーショナル・モナドについてその作成者のH. Apfelmusが、彼の記事で詳しく説明している。この記事では、stackの操作を例にとって、その解釈・実行部分(interpret)を説明している。ここでは、その説明を長さ注釈付きリストに応用する。

2.プログラム

プログラムは命令の列とし、最初の命令は[ ]とする。プログラムは、一つの命令だけでも構わないし、複数の命令がつながったものでも構わない。例を挙げる。長さ注釈つきリストに対する命令をNilと(Cons a)にすると、
example1 = Cons 5 : Cons 3 : Cons 1 : [ ]
は一つのプログラムである。例えば、長さ注釈つきリスト([6,3], 2)にこのプログラムを施すと新しい長さ注釈つきリスト([5,3,1,6,3], 5)を得る。

二つのプログラムをつなぎ合わせる関数を(++)とする。もう一つのプログラムを
example2 = Cons 6 : Cons 7 : Cons 1 : [ ]
とし、前のプログラムとつなぎ合わせると次のプログラムexample3を得る。
example3=example2 ++ example1 = Cons 6 : Cons 7 : Cons 1 : Cons 5 : Cons 3 : Cons 1 : [ ]

empty = [ ]とし、is,js,ksをプログラムとすると、プログラムは次の性質を有する。

empty ++ is    = is                 --左単位元
is ++ empty    = is                 --右単位元
(is + js) + ks = is + (js + ks)     --結合律

3.プログラムの解釈

プログラムを命令の列とし、次のように定義する。

type Program instr = [instr]

長さ注釈付きリストに対する命令は、次のようになる。(なお、ここでは、整数のリストに限定する。)

data ListInstruction = Nil | Cons Int

この結果、長さ注釈付きリストに対するプログラムは、次のようになる。

type ListProgram = Program ListInstruction

また、長さ注釈付きリストを次のように定義する。

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

プログラムの解釈・実行を行うinterpretは次のように実装する。

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

上記のinterpretを用いての実行例は以下の通りである。

main :: IO ()
main = putStrLn $ displayList $ interpret example (List {content = [4,2], length' = 2})

論理の世界だけで、長さ注釈つきのリストに対する解釈・実行ができたので、これまで説明したオペレーショナル・モナドを必要としないように見える。

しかし、命令によっては実行結果を返すものがある。長さ注釈つきリストの命令は結果を返さなかったが、H. Apfelmusがオペレーショナル・モナド記事では、スタックを例にしている。スタック命令のPopは、スタックからその先頭のデータを取りだしてそれを返す。一般に命令は実行した後値を返すが、その戻り値を後で使いたい場合がある。その場合には、論理の世界だけで実装することは不可能である。

長さ注釈付きリストの場合でも、Cons aを実行した後で、リストの長さを出力として返すようにするとスタックと同じような状況が生じ、論理の世界だけで処理することは難しくなる。そこで、オペレーショナル・モナドに登場してもらう。

その前にここまでのプログラムの全体を示す。

{-# LANGUAGE GADTs #-}

type Program instr = [instr]
type ListProgram = Program ListInstruction
data ListInstruction = Nil | Cons Int
data List s n = List {content :: [Int], length' :: Int} deriving Show
displayList x = show (content x, length' x) ++ "\n"

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


example = Cons 5: Cons 3 : Cons 1 : []

main :: IO ()
main = putStrLn $ displayList $ interpret example (List {content = [4,2], length' = 2})