第6回　局所的な「状態」を利用するためのStateモナド

　プログラムを書いている中で，多くの式で同じ値を使いまわしていたり，値の変化に一定のパターンが生じていることに気づくかもしれません。こういう時，式に局所的（local，ローカル）な「状態（State）」があれば，プログラムをすっきり書くことができると思うのではないでしょうか？ 実際にLispにはsetf（Schemeならset!）という変数の値を書き換える機能があり，OCamlなどのML系の言語には参照型（reference type，リファレンス型）という値の再代入を許す特別な変数を扱う機能があります。

　しかし，残念ながらHaskellのように純粋な関数型（purely functional）を標榜している言語には，このような書き換え可能な変数を持つことは基本的に許されていません。書き換え可能な変数があると，「状態」の更新が複数個所で共有され，「プログラムを局所的にではなく，大域的（global，グローバル）に考える必要が出てくる」＝「副作用が生じる」可能性があるためです（参考リンク）。そうなれば当然，「同じ式は必ず同じ結果を返す」という参照透過性（referential transparency，参照透明性）は崩れてしまいます。

　そのため，Haskellでは，このような機能を持つデータ型は，IOモナドなどのごく限られた範囲でのみ使えるよう制限を課しています。IOを用いることで，コンテナの外に参照型を漏れ出させないようにしているわけです。

　でも，それでは状態を持つようなコードを書こうとしたら最後，IOを持ち運ぶことになってしまって不便です。どうにかならないでしょうか？

　少し見方を変えてみましょう。ここで問題なのは，いわゆる局所的な「状態」を保持するデータ型が欲しいが，参照型のような書き換え可能な変数を無制限に導入してしまうと大域的に「状態」を保持するようなプログラムを書いてしまう危険性がある，ということです。そうであれば，“参照型ではない何者か”に参照型の機能をエミュレートさせて，まるで参照型であるかのように振舞ってもらえばよいのではないでしょうか？

　これを実現するのが今回説明するStateモナドです。Stateモナドは，「状態」を持たないプログラムをあたかも「状態」を持っているかのように記述するための糖衣構文です。

Stateモナドの実装

　Stateモナドは，標準Haskellで定義されているライブラリではありません。Haskellの多くの基本的なライブラリが収録されているbaseパッケージにも入っていません。mtl（A monad transformer library）というパッケージに収録されています。とはいっても，mtlは基本的なライブラリとして多くの処理系にバンドルされているので，通常は特に別途インストールする必要はありません。

　ただ，mtlがバンドルされていないケースもあるので注意してください。HugsのWindows版バイナリのうち，MinHugs-*という名前で提供されている最低限のライブラリだけ収録したものがそれに当たります。また，配布されているGHCのソースコードにバンドルされているCore Librariesにもmtlは収録されていません。mtlパッケージはExtra Librariesとして扱われています（Core LibrariesやExtra Librariesといった名前は暫定的なものであり，言語処理系の持つコア機能とそれ以外の機能を区別する呼び名ではない点に注意してください）。

　GHCを使っている場合には，処理系にmtlが含まれているかどうかをあらかじめ確かめておくとよいでしょう。ghc-pkgのlistコマンドを使うことで，使用している処理系が持つパッケージの一覧を見ることができます。

$ ghc-pkg list
C:/ghc/ghc-6.6\package.conf:
    Cabal-1.1.6, Crypto-3.0.3, FilePath-0.1.0, GLUT-2.0, HDBC-1.0.1,
    HDBC-sqlite3-1.0.1.0, HTTP-2006.7.7, HUnit-1.1, NewBinary-0.1,
    OpenGL-2.1, Pan-0.1, QuickCheck-1.0, Win32-2.0, afrp-0.4, base-2.0,
    cgi-2006.9.6, fgl-5.2, (ghc-6.6), haskell-src-1.0,
    haskell-src-exts-0.2.1, haskell98-1.0, haskelldb-0.10,
    haskelldb-hdbc-0.10, haskelldb-hdbc-sqlite3-0.10, html-1.0,
    hxt-6.1, lcs-0.1, mtl-1.0, network-2.0, objectio-1.0, parsec-2.0,
    readline-1.0, regex-base-0.71, regex-compat-0.71, regex-posix-0.71,
    rts-1.0, stm-2.0, template-haskell-2.0, time-1.0, wx-0.10.1,
    wxcore-0.10.1, xhtml-2006.9.13

　この例では，下から4行目にmtlという名前が表示されているのがわかると思います。

　mtlはCabalでパッケージ化されているので，処理系にmtlが入っていない場合には第2回のコラムで説明したData.ByteStringのインストール方法を参考にインストールしてください。mtlはghc-(version)-src-extralibs.tar.bz2という名前のアーカイブに入っています（ダウンロード・ページ）。あるいはバージョン管理システムのdarcsを使い，http://darcs.haskell.org/packages/mtl/から取得しても構いません。

　なお，Stateを含めmtlに収録されている多くのモナドの代替実装として，monadLibというライブラリもあります。

　さて，それではStateモナドの実装を見てみましょう。mtlのStateモナドは，Control.Monad.Stateモジュールの中で定義されています。

newtype State s a = State { runState :: s -> (a, s) }

instance Monad (State s) where
	return a = State $ \s -> (a, s)
	m >>= k  = State $ \s -> let
		(a, s') = runState m s
		in runState (k a) s'

　「これが本当に参照型の機能を実現するコードなのか？」と狐につままれたような感じがするかもしれませんが，そんなに難しくはありません。一つ一つ読み解いていきましょう。

　Stateはs -> (a, s)という型を持つ関数を格納するコンテナです。

　Stateモナドのreturnは，aという値から\s -> (a, s)というラムダ抽象を作り出し，Stateに格納する，という定義になっています。値aの型をa，値sの型をsとすると，returnによってまさにs -> (a, s)という型を持つ関数がStateに格納されることになります（つまり，ここで格納されたaという「値」は，Stateというコンテナから直接取り出すことはできません。取り出す際には，必ず「状態」sを与えてやる必要があります）。

　ここで格納した関数は，パターン照合だけではなく，runStateという「フィールド・ラベル（field label）」を利用することでも取り出すことができます（参考リンク）。

Prelude Control.Monad.State> :t runState (return 12)
runState (return 12) :: (Num a) => s -> (a, s)

　このとき，runStateに関数とともに「関数で使われる初期状態」を値として与えてやることによって，（最終的な「値」，最終的な「状態」）のペアを返す計算を行わせることができます。このような特徴からユーザーにとってrunStateは，Stateモナドを使って行った計算の結果できたコンテナを実際に使用するための関数とみなすことができるでしょう。

Prelude Control.Monad.State> :t runState (return 12) 11
runState (return 12) 11 :: (Num t, Num s) => (t, s)
Prelude Control.Monad.State> runState (return 12) 11
Loading package mtl-1.0 ... linking ... done.
(12,11)

　runStateの返す「値」と「状態」のうち，片方だけが必要な場合もそう少なくはないでしょう。こうしたときのことを考慮して，評価した結果の「値」だけを返すevalStateと，実行された「状態」のみを返すexecStateという二つの関数が用意されています。それぞれ以下のように定義されています。

evalState :: State s a -- The state to evaluate
	  -> s         -- An initial value
	  -> a         -- The return value of the state application
evalState m s = fst (runState m s)

execState :: State s a -- The state to evaluate
	  -> s         -- An initial value
	  -> s         -- The new state
execState m s = snd (runState m s)

　関数の定義を見ればすぐに気付くと思いますが，fstはペアの第1要素を取り出す関数，sndはペアの第2要素を取り出す関数です。

　これでreturn及びrunStateについて説明しました。すぐに>>=の定義に戻らずに，いつものように先にfmapの定義を見ておきましょう。Stateに対するmapは以下のように定義されています。

instance Functor (State s) where
	fmap f m = State $ \s -> let
		(a, s') = runState m s
		in (f a, s')

　let式の後のinはlet式の一部で，inの後にlet式を使って束縛した一連の変数を使って実際に計算を行う式が続きます。実はlet式の一般形は「let { d1 ; ... ; dn } in e」で，これまで使ってきたlet式はdo記法などの特別な構文内でのみ使用可能な糖衣構文です（参考リンク）。

　fmapの引数である関数fは，runStateによって計算を行った後の「値」である変数aにだけ適用されているのがわかると思います。では，fmapと>>=と比べてみましょう。

instance Monad (State s) where
	m >>= k  = State $ \s -> let
		(a, s') = runState m s
		in runState (k a) s'

　>>=は，joinとして2回目のrunStateを使った計算を行うため，1回目のrunStateによって求められた「状態」が更新される可能性があります。よって，>>=を使うことで複数のStateモナドを使った計算をつなぎ合わせることができるのです。

　なお，StateモナドにおけるFunctorクラスおよびMonadクラスのインスタンスはState sという型変数を一つ保持するものとなっているため，処理系に特別な拡張がなくても種の不一致が問題になることはありません。

Prelude Control.Monad.State> :k State
State :: * -> * -> *
Prelude Control.Monad.State> :k State Int
State Int :: * -> *
Prelude Control.Monad.State> :k State Bool
State Bool :: * -> *