Stateモナドの定義の理解
Stateモナドの定義を確認します。
newtype State s a = State { runState :: s -> (a, s) }
なんで、 s->(a, s)という形なのかずっと疑問でした。
...
次のように考えるとよいかと思いました。
まず、b -> aという計算を考えるとします。この計算にともなって、状態を変更することを考えます。
そのためには、元々の計算と、状態の変更（＝計算）も一緒に行えば、見かけ上は、状態の管理が出来るといえます。
そこで、タプルで表現をしてみます。
(b, s) -> (a, s)
とします。b->aという計算をするけど、合わせて、s -> sという状態の更新を行うという解釈です。
...
ここまでを、頭においておいて、Stateモナドの定義を再掲します。
newtype State s a = State { runState :: s -> (a, s) }
s -> (a, s)で、実態は関数です。sは状態を示す型なので、->の左辺が状態が変わる前、右辺が状態が変わった後になります。aは変わった状態と一緒に計算される結果の値と解釈します。
そして、状態が変わる前の計算に必要な入力の値の型をbとします。
ここで、状態が変わる前と、stateモナドの実態である関数を->で（無理やり）つなげてみます。
b -> s -> (a, s)
となります。これを書き換えます。
(b -> s) -> (a, s)
bとsが与えられたら、(a, s)が出力されると見なせるので、さらに、書き換えます。
(b, s) -> (a, s)
すると、最初に考えた、状態管理の式と同じになります。逆に辿ればStateモナドの定義を導くことが出来ると思います。
元ネタはこちら：
Mike's World-O-Programming - Yet Another Monad Tutorial (part 7: state monads)
