読者です 読者をやめる 読者になる 読者になる

さんぽみち

なにか思いついたときとかに気まぐれに更新されます。

Stateモナドは一度実装すべき

はじめに

そういや Haskell で State モナドの挙動をちゃんと理解してなかったなぁと思ったのでとりあえず別言語で実装してみたらすんなり理解できた話。
チュートリアルを書きたいわけではないので、自分がなぜ理解に苦しんだのかについて焦点を当てたいと思います。

実装

Ruby で書きました。
短いので意味をかみしめながらでも短時間で実装できます。
テストはみんな大好きスタックの実装!
空になった後とか push 直後とか雑だけど目的が実装の理解なので目をつむってください。
State.rb

class State
  def self.unit(v)
    state{|s| next v, s }
  end
  def self.state(&g)
    self.new(g)
  end
  def self.get
    state{|s| next s, s }
  end
  def self.put(s)
    state{|_| next nil, s }
  end
  
  attr_reader :g
  def initialize(g)
    @g = g
  end
  def bind(&f)
    State.state{|s|
      v, ns = @g.call(s)
      f.call(v).g.call(ns)
    }
  end
  def runState(s)
    @g.call(s)
  end

  def >=(f)
    bind(&f)
  end
end

test.rb

require('./State.rb')

def pop
  State.state{|s| next s.last, s[0...s.length - 1] }
end
def push(v)
  State.get.bind{|s| State.put(s << v) }
end

# run
push(1)
  .bind{|_| push(2) }
  .bind{|_| push(3) }
  .bind{|_| push(4) }
  .bind{|_| push(5).bind{|_| pop } }
  .bind{|v| p v; pop }
  .bind{|v| p v; push(10).bind{|_| pop} }
  .bind{|v| p v; pop }
  .bind{|v| p v; pop }
  .bind{|v| p v; pop }
  .bind{|v| p v; pop }
  .bind{|v| p v; pop }
  .runState([])

結果

5
4
10
3
2
1
nil

何がわかりづらかった?

伝搬するのは状態でなく関数であること

このモナドは、バインド関数によって関数を合成しながら引き継いでいきます。
状態を取りまわせるという触れ込みで変な先入観がうまれて理解を妨げていたっぽいです。

与えられる値は前回指定し、値を利用後に次の値を取り出す方法を指定する

do記法で書くと違和感なく使えるけど、理解するためにすべて演算子に落として考えた時にずれているのがややこしいです。

実装した感想

まず、状態から取り出した値をどのように渡すかがわかりやすいです。
なにせ自分で渡してますので。
あとは runState で渡した状態情報が吸いあがって最初の関数から順番に適用されていく感覚がつかめて結構楽しいかも。
この二点が主な収穫で、状態情報と実装が完全に切り離されて参照透過なまま状態情報を共有できていることへの理解が深まりました。

おまけ

>>= 演算子と似てるなーってことで >= 演算子をオーバーライドして bind 関数をラップしてやったけど、これを使ってアロー演算子ラムダ式を定義してバインドしてやると

( pop \
  >=-> v{ p v; pop } \
  >=-> v{ p v; pop } \
  >=-> v{ p v; pop } \
  >=-> v{ p v; pop }
).runState([1,2,3,4])

って書けます。
なんかかっこいい!!

参考

タマニチェンコ様(2014)Stateモナドがわかればモナドがわかる - セカイノカタチ

 bind 関数の実装で参考にさせていただきました。
 技術の話をしながらもユーモアに富んだ楽しい記事を書かれています。
 同ページにリンクのあるIOモナドの図解も、笑いながら理解に輪郭を与えてくれる素敵な記事です。