State モナド

何が問題なのか

1. 状態だけを入出力する関数を作っても意味が無い
   なんとなく状態を入力としてそれに基づいて新しい状態を出力する関数を作って繋げていけば関数型プログラムでも状態の変化を表現できそうだが、関数型プログラムは副作用を及ぼさないため本当に状態だけぐるぐる回ることになりこれでは意味が無い
2. タプルは直接繋げられない
   じゃあ、タプルを使えば状態と入出力データをペアで扱えると思うが、f→[タプル]→gと直接繋げることは出来ずf→(a,s)→gと一旦変数に格納しないといけない
3. 変数の破壊的代入が出来ない
   別にタプルを変数に格納しても問題ないように思えるが、関数型プログラムでは変数の破壊的な代入が出来ないため、f→(a,s)→g→(b, s')→h→(c,s'')→と毎度状態を示す変数sをリネームしていかないといけなくなる

裏で状態の受け渡しを行う

そこで、Stateモナドでは表向きは入出力データの受け渡しのみを行い、その裏でStateモナドが状態の受け渡しを行う。
具体的な動作を理解するため、前回と同じく同様の動作をするコードをJavaScriptで書くと以下のようになった。

var State = {
  return: function(a) {
    return State.State(function(s) {
      return Touple(a, s);
    });
  },
  State: function(x) {
    return {
      bind: function(f) {
        return State.State(function(s) {
          var tmp = x(s);
          return runState(f(tmp.lhs), tmp.rhs);
        });
      },
      inner: x
    }
  }
}

var runState = function(state, a) {
  return state.inner(a);
}

var Touple = function(left, right) 
{
  return { lhs: left,rhs: right }
}

基本的には前回のListモナドと同じだが、Stateモナドの場合コンストラクタの引数(?)は関数で、これは値aと状態sを引数としてこれから新しい値a'と新しい状態s'のタプルを生成する関数f
f(a,s) -> (a',s')
があったとして、これを第一引数aでカリー化した関数f'
f'(s) -> (a',s')
を与えて生成する。
例えば、

var f = function(a) {
  return State.State(function(s) {
    return Touple(a+s, s+1);
  });
}

var g = function(a) {
  return State.State(function(s) {
    return Touple(a*s, s+a);
  });
}

var t = runState( f(1).bind(g), 2);

とすれば、
(a=1, s=2) →f()→(a'=a+s=3, s'=s+1=3)→g()→(a''=a'*s'=9,s''=s'+a'=6)
と期待通りの結果が得られる。

また、runStateはbindにより生成されたStateモナド内部の関数を実行して出力と状態を得る関数になる。

作りそのものはListモナドとあまり変わらないのだが、動きは非常に複雑なので頑張って図示すると以下のようになる。

まず関数ｆを入力aでカリー化してsを入力として(a',s')を出力する関数f'を内部関数として持つStateモナドを生成する。
これに関数gをバインドして新しいStateモナドを生成する。このモナドはbind関数の中で生成される関数(仮にinnerとする)を内部関数として持ち、innerはf'とgを内部に持っている。
このモナドに対して状態sを与えてrunStateすると、inner関数が呼び出される。inner関数では、状態sをf'に適用して、a'とs'を得、今度はa'をgに適用する。
gはfと同じくa'でカリー化したg'を持つStateモナドを生成する。
inner関数ではこの生成されたStateモナドに対して先ほどの状態s'を与えてrunStateすると最終的にg'にs'が適用されることになる。

このように、表向きはfとgの間では入出力だけをやりとりしているように見せつつ、StateモナドがrunStateを使って裏で状態の受け渡しを行っている。

今回もわかりやすいようにStateオブジェクトにbindをぶら下げたが、関数オブジェクトにbindをぶら下げればちょっとシンプルにかける。

var State = function(x) {
  x.bind = function(f) {
    return State(function(s) {
      var tmp = x(s);
      return runState(f(tmp.lhs), tmp.rhs);
    });
  }
  return x;
}
State.return = function(a) {
  return State(function(s) {
    return Touple(a, s);
  });
}

var runState = function(state, a) {
  return state(a);
}

もののついでなので、get/put/gets/modify/push/popも実装してみた。大体ルールがわかってきたので、Haskellのコードをそのまま置き換えれば動いた。

var get = function() {
  return State(function(s) {
    return Touple(s, s);
  });
}

var put = function(s) {
  return State(function() {
    return Touple(null, s);
  });
}

var gets = function(f)
{
  return get().bind(Combine(State.return, f));
}

var modify = function(f)
{
  return get().bind(Combine(put, f));
}

var Concat = function(val, arr) 
{
  var newArr = new Array(arr.length+1);
  newArr[0] = val;
  for(var i = 0; i < arr.length; i++) {
    newArr[i+1] = arr[i];
  }
  return newArr;
}

var Head = function(arr) {
  return arr[0];
}

var Tail = function(arr) {
  var newArr = new Array(arr.length-1);
  for(var i = 0; i < newArr.length; i++) {
    newArr[i] = arr[i+1];
  }
  return newArr;
}

var push = function(a)
{
  return modify(function(arr) 
  {
    return Concat(a, arr);
  });
}

var pop = function()
{
  var value;
  return MonaDo(gets(Head),
  [
    function(x_) { value = x_; return modify(Tail); },
    function(x_) { return State.return(value); }
  ]);
}

var t = runState( pop(), [1,4,5]);

popについては展開するのが面倒なのでさらについでにdo記方も作ってみたが、これもほぼほぼHakellの定義通りで出来る。（letはそのままは無理だがそれなりに書きようはある）

var MonaDo = function(m, fs) {
  if(fs.length > 2) {
    return m.bind(function(a) {
      return MonaDo(fs[0](a), fs.slice(1));
    });
  } else {
    return m.bind(function(a) {
      return fs[0](a).bind(fs[1]);
    });
  }
}