bitterharvest’s diary

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

通常のプログラムをHaskellで記述する(3)

11.3 状態を表現するための準備をする

Haskellで状態を表すための準備をしよう。入力\(a\) を受けてその結果得られた状態\(s\)をタプル\( (a, s) \)であらわすことにしよう。

Hskellでプログラムを書くときは、しっかりと腰を据えて考えることが必要である。思い付きで記述したとしても、コンパイラで跳ねつけられてしまう。昨日は、車を運転しながらプログラムを考えていたので、青信号になったのに気が付くのが遅かったり、駐車場の入り口を通り過ぎたりと散々であった。事故を起こさなくてよかったが、やはり、書斎でじっくり考えて、納得してからプログラムの記述という肉体労働を始めるのがよい。

まずは、状態というデータ型を考えることにしよう。

入力が\(a\)から\(b\)に変わったとしよう。これを\(a \rightarrow b\)で表す。あるいは、\(f : a \rightarrow b\)と考えて、\(a\)から\(b=f(a)\)になったと考えてよい。そこで、入力と状態\(s\)のタプルはを考えることにしよう。これは入力が変化するとき、タプルの変化は\( (a, s) \rightarrow (b, s) \)となる。もちろん、左側の\(s\)と右側の\(s\)でも値は異なっていてよい。しかし、データ型は同じなので、同じ\(s\)で記述されていることに注意してほしい。

さて、\( (a, s) \rightarrow (b, s) \)はカリー化することで\(a \rightarrow (s \rightarrow (b,s))\)と書くことができる。このようにすると、\(s \rightarrow (b,s)\)の部分がだいぶ前の記事で出てきた\(Reader\)に似ていることに気がつかないだろうか。

\(Reader\)での可換図式に真似て、\(a \rightarrow (s \rightarrow (b,s))\)の可換図式を書くと次のようになる。
f:id:bitterharvest:20170825180411p:plain

この可換図式から\(a\)が射\(s \rightarrow (a,s)\)に関手によって移されていることが分かる。この時の関手を\(State \ s\)としよう。即ち、\(State \ s \ a = State(s \rightarrow (a,s))\)であり、\(State \ s \ b = State(s \rightarrow (b,s))\)である。そこで、これをデータ型にしてみよう。次のようになる。

State s a = State (s -> (a,s))

ここで、\(s\)は状態を表している。与えられた状態が入力とともに返されるのがこのデータ型の特徴である。これによって、状態を関数の間で持ち回ることが可能になる。

また、関数\(f\)は関手によって\(State \ s \ f = fmap \ f \)に移される。

そこで、関手\(State \ s\)をクラス\(Functor\)のインスタンスとして定義しよう。

instance Functor (State s) where
    fmap f (State g) = State (\s -> let (a, sa) = g s
                                    in ( f a, sa))

このプログラムでは、\( fmap \ f \ (State \ g)\)を求める。これは\(s\)から\( (b,s)\)への射である。上記のプログラムで、\( (b,s)\)は\( (f \ a,sa)\)である。\( (a,s)\)を、プログラムでは\( (a,sa)\)を、経由して求めている。

それでは、これをモナドとして定義しよう。定義する関数は\( (>>=)\)と\(return\)である。\( (>>=)\)の型シグネチャは\(m a -> (a -> m b) -> m b\)である。今回は、\(m = (State \ s)\)なので、置き換えると\(State \ s \ a -> (a -> State \ s \ b) -> State \ s \ b\)となる。即ち、\(State( s \rightarrow (a,s))\)を入力する。次に関数\( (a -> State \ s \ b)\)を実行する。この関数への入力は\(State( s \rightarrow (a,s))\)ではなく\(s \rightarrow (a,s)\)である。そして、この関数は\(State( s \rightarrow (b,s))\)を出力する。さらに、これが\( (>>=)\)の出力ともなる。

この関数を定義する前に、データ型Stateの値を得て、即ち\(State( s \rightarrow (a,s))\)を得て、これに\( s\)を得て、\( (a,s)\)を得る関数\(runState\)を定義しておこう。

runState :: State s a -> s -> (a, s)
runState (State f) s = f s

これを利用すると\( (>>=)\)は次のようになる。

    ma >>= k = State (\s -> let (a, sa) = runState ma s 
                            in runState (k a) sa)

このプログラムで\(k\)は上記の説明での関数\( (a -> State \ s \ b)\)である。これを利用するとモナドの定義は次のようになる。

instance Monad (State s) where
    ma >>= k = State (\s -> let (a, sa) = runState ma s 
                            in runState (k a) sa)
    return a = State (\s -> (a, s))

これで終わりなのだが、新しいHaskellではクラス階層の中で、\(Functor\)と\( M onad \)の間に、\(Applicative\)が定義されている。そこで、これを定義する。次のようになる。

instance Applicative (State s) where
    pure a = State (\s -> (a, s))
    (<*>) mf ma = State (\s -> let (a, sa) = runState ma s
                                   (f, sb) = runState mf sa
                               in ( f a, sb))

\(Applicative\)では\(pure\)と\( (<*)\)を定義する必要がある。このプログラムでは必要ないので、\(pure \ a = undefined\)そして\((<*>) \ mf \ ma = undefined\)でも構わない。

モナドを定義できたので、次回は銀行のATMのプログラムを完成させよう。