1. Kitam

    Posted

    Kitam
Changes in title
+TypeScriptでState Monadを実装する
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,157 @@
+HaskellとJavaScriptの学習を兼ねて、TypeScriptでState Monadを実装してみた。
+Monad理解への第1歩は、State Monadに限る(ということにしよう)。
+
+今回の目標
+----------------
+TypeScriptでState Monadを実装し、副作用のないスタックを実装する。
+
+TypeScript
+----------------
+<http://www.typescriptlang.org/>
+
+特徴
+
+* Microsoft製のJavaScriptのスーパーセット
+* 静的型付け言語(ジェネリックスがある!)
+* クラス
+* アロー関数式
+
+今回は静的型付けが重要。
+これがないと引数の意味が伝わらない。
+今回初めて使用する。
+
+State Monad(Haskell)
+----------------
+特徴
+
+* 状態付き計算を保管することで、副作用を無くす。
+
+State Monad関連の実装する部分
+
+```hs:Haskell
+newtype State s a = State { runState :: (s -> (a,s)) }
+```
+
+```hs:Haskell
+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'
+```
+
+```hs:Haskell
+evalState m s = fst ( runState m s )
+execState m s = snd ( runState m s )
+```
+
+```hs:Haskell
+instance MonadState (State s) s where
+ get = State $ \s -> (s,s)
+ put s = State $ \_ -> ((),s)
+```
+
+
+State Monad(TypeScript)
+----------------
+
+まずは、runStateが最終的に返す「値」と「状態」を保持するタプルを定義する。
+
+```ts:TypeScript
+interface Tuple2<A,B> {
+ fst: A
+ snd: B
+}
+```
+
+TypeScriptには`interface`とジェネリックスがあるので、型安全なオブジェクトが簡単に定義できる。
+これで型宣言が少し楽になる
+
+次はStateクラスを定義
+
+```ts:TypeScript
+class State<T,X>{
+ runState: (t:T) => Tuple2<X,T>
+ evalState = (t:T):X => this.runState(t).fst
+ execState = (t:T):T => this.runState(t).snd
+ constructor(g:(t:T) => Tuple2<X,T>){
+ this.runState = g
+ }
+ static returns<T,X>(v:X):State<T,X>{
+ return new State<T,X>((t:T) => { return {fst:v, snd:t } })
+ }
+ bind<B>(f: (X) => State<T,B>):State<T,B>{
+ var g = (t:T) => {
+ var st = this.runState(t)
+ return f(st.fst).runState(st.snd)
+ }
+ return new State<T,B>(g)
+ }
+}
+```
+
+Haskell版State Monadの`return`、`>>=`は、TypeScript版では`returns`、`bind`メソッドとした。
+TypeScriptの静的型付けにより、引数に関数を指定しても分かりやすい。
+
+続いて、MonadStateを実装する。
+Haskell版MonadStateとほぼ一緒。。。`null`。。。が。。。
+
+```ts:TypeScript
+class MonadState {
+ static get<T>():State<T,T> {
+ var g = (t:T) => {
+ return { fst: t, snd: t }
+ }
+ return new State<T,T>(g)
+ }
+ static put<T>(a:T):State<T,void> {
+ var g = (t:T) => {
+ return { fst: null, snd: a }
+ }
+ return new State<T,void>(g)
+ }
+}
+```
+
+スタックの準備は完了。
+
+スタックから取り出す関数を定義する。
+
+```ts:TypeScript
+var pop = <X>():State<X,X[]> =>
+ MonadState.get<X[]>()
+ .bind(e => { return MonadState.put<X[]>(e.slice(1))
+ .bind(k => State.returns(e[0])) })
+
+```
+
+現在の値を取得し、二番目以降のデータを保存し、先頭のデータを返す。
+
+スタックに値を設定する関数を定義する。
+
+```ts:TypeScript
+var push = <X>(i:X):State<X,X[]> =>
+ MonadState.get<X[]>()
+ .bind(e => MonadState.put<X[]>([i].concat(e)))
+```
+
+テスト
+
+```ts:TypeScript
+var fnc = <X>():ms.monad.state.State<X,X[]> =>
+ pop()
+ .bind(e => pop())
+ .bind(e => push(20))
+ .bind(e => pop())
+ .bind(e => push(e*5))
+
+console.log(fnc().execState([1,2,3])) //=> [100,3]
+```
+
+期待した値が返った
+
+まとめ
+----------------
+静的型付け(型推論)が良い(CoffeeScriptも静的型付けにならないものか)
+TypeScriptは早期開発より、手堅さ優先の言語という印象
+無駄な労力を使った気がしなくもないが、State Monadの理解が少し深まる。
+しかし、let定義できないし、このままの実装では使えない(笑)