Play2.0のIterateeを理解したい

Play2.0がついにリリースされました。早速ダウンロードしてかねてより興味のあったWebSocketで遊んでみようとしたところIteratee/Enumeratorなるものにぶち当たりました。
とりあえずソースを見てみるもののさっぱり理解できず、google先生に泣きついたところどうやらHaskellから来た概念のようで日本語の解説としては以下のページを教えてもらいました。

iterateeとは何か、何が良いのか
Enumerator Package – Yet Another Iteratee Tutorial
使ってみよう Enumerator

現時点での理解をもとに簡単な関数から初めてPlay2.0のIterateeに迫ってみたいと思います。

Inputとstep関数

Iterateeは「入力を受け取り何かをする」ということを抽象化したものだそうです。
というわけでまず入力を表すInputを作ってみました。

sealed trait Input[+E] {
}

object Input {
  case class El[+E](e: E) extends Input[E]
}

次に計算結果を表すInt型の変数とInput[Int]を受け取って何かする関数stepを考えます。
例えばこんな感じ、

def step(result:Int)(in:Input[Int]):Int = in match{
  case Input.El(e) => {println(e); result + e}
} 

入力を表示して、計算結果に足し合わせて返すだけです。
以下のように使えます。

scala> var res:Int = _
res: Int = 0

scala> res = step(res)(Input.El(1))
1
res: Int = 1

scala> res = step(res)(Input.El(2))
2
res: Int = 3

scala> res = step(res)(Input.El(3))
3
res: Int = 6

さすがに返される計算結果をいちいち変数に入れるのは格好悪いので、foldLeftを使ってみます。

scala>   val l = List(1,2,3).map(Input.El(_))
l: List[MyIteratee.Input.El[Int]] = List(El(1), El(2), El(3))

scala>   l.foldLeft(0)((r, e) => step(r)(e))
1
2
3
res7: Int = 6

かなりすっきりしました。

Iteratee登場

しかしまだ不満があります。そもそも、計算結果をいちいち外に返してしまうのはよろしくない感じなので、stepの実行と計算結果をワンセットで保持するIteratee[E,A]を定義します。
IterateeはInputを引数にとってstepを駆動し、Iterateeを返すメソッドfeedを持つものとします。

trait Iteratee[E, A] {
  def feed(in:Input[E]):Iteratee[E,A]
}

先ほどのstepをIterateeを返すようにして、さらにstepを内包する形でIterateeを作成してやるとこうなります

val it:Iteratee[Int,Int] = new Iteratee[Int,Int]{
  def step(result:Int)(in:Input[Int]):Iteratee[Int,Int] = in match{
    case Input.El(e) => {
      println(e)
      new Iteratee[Int, Int]{
        def feed(in:Input[Int]):Iteratee[Int,Int] = 
	  step(result + e)(in)
	}
      }
    }

  def feed(in:Input[Int]):Iteratee[Int,Int] = 
    step(0)(in)
}

stepが呼ばれるとこの次に実行するstepを含むIterateeを新たに作って返すのがポイントです。
実行してみます。foldLeftの初期値として上で作ったitを渡しています。

scala>   val l = List(1,2,3).map(Input.El(_))
l: List[MyIteratee.Input.El[Int]] = List(El(1), El(2), El(3))

scala>   l.foldLeft(it)((res, e) => res.feed(e))
1
2
3
res1: Iteratee[Int,Int] = $anon$1$$anon$2@3e1dfb2

Iterateeが計算結果を返せるようにする

計算結果をいちいち外に漏らさなくなったのは良いのですが、計算結果に全くアクセスできなくなってしまいました。
計算を終えたら結果を取得できるようにしてみましょう。入力の終わりを表すInput.EOFを定義して、Input.EOFを受け取ったらrunというメソッドで計算結果を受け取れるようにします。

sealed trait Input[+E] {
}

object Input {
  case class El[+E](e: E) extends Input[E]
  case object EOF extends Input[Nothing]
}

次にIterateeです。

trait Iteratee[E, A] {
  def feed(in:Input[E]): Iteratee[E,A]
  def run(): A
}

val it:Iteratee[Int,Int] = new Iteratee[Int,Int]{
  def step(result:Int)(in:Input[Int]):Iteratee[Int,Int] = in match{
    case Input.El(e) => {println(e);
      new Iteratee[Int, Int]{
        def feed(in:Input[Int]):Iteratee[Int,Int] = 
	  step(result + e)(in)
	def run() = this.feed(Input.EOF).run()
      }
    }
    case Input.EOF => {
      new Iteratee[Int, Int]{
        def feed(in:Input[Int]):Iteratee[Int,Int] = 
	  sys.error("diverging iteratee after Input.EOF")
	def run() = result
      }
    }
  }

  def feed(in:Input[Int]):Iteratee[Int,Int] = 
    step(0)(in)

  def run() = this.feed(Input.EOF).run()
}

Input.EOFを受け取る前にrunが呼ばれた場合は一端thisにInput.EOFを渡した後で、runを呼ぶようにしています。

fold導入

上で書いたstepを見てもらうと、Input.ElとInput.EOFを渡したときで異なるIterateeを作って返しています。
それぞれ、「計算中の状態」と「計算終了の状態」を表していると考えることができます。

ここで少々天下りですが、Iterateeに状態ContとDoneを導入します。Contはまだ計算中であることを表し、Doneは計算が終了したことを表すこととします。
さらにメソッドfoldをIterateeに持たせます。foldはcontとdoneというそれぞれ状態がContだった時、Doneだった時に実行する処理を与えることができます。

trait Iteratee[E, A] {
  def fold[B](done:(A, Input[E]) => B,
              cont:(Input[E] => Iteratee[E,A]) => B): B
  // ...
}

doneの型はさておきcontの型はstepを駆動させることが想定されています。

Condはfoldでcondが実行される状態、Doneはdoneが実行される状態と考えると、それぞれの状態を作り出すobjectは次のように実装されます。

  object Cont{
    def apply[E, A](k: Input[E] => Iteratee[E, A]): Iteratee[E, A] = new Iteratee[E, A] {
      def fold[B](done: (A, Input[E]) => B,
		  cont: (Input[E] => Iteratee[E, A]) => B
		  ): B = cont(k)
    }
  }

  object Done {
    def apply[E, A](a: A, e: Input[E]): Iteratee[E, A] = new Iteratee[E, A] {
      def fold[B](done: (A, Input[E]) => B,
		  cont: (Input[E] => Iteratee[E, A]) => B): B = done(a, e)
    }
  }

なんか狐にでもつままれたような感じですが…関数型言語すごいよ関数型言語
Iterateeのfeedやrunはfoldで書くことができます。

  trait Iteratee[E, A] {
    def fold[B](done:(A, Input[E]) => B,
		cont:(Input[E] => Iteratee[E,A]) => B): B

    def feed(in:Input[E]): Iteratee[E,A] =
      fold( (a,e) => Done(a,e),
	   k => k(in))

    def run():A =
      fold((a, _) => a,
	   k => k(Input.EOF).fold( (a1, _) => a1,
				  _ => sys.error("diverging iteratee after Input.EOF")))
  }

入力を足し合わせるIterateeは次のようになります。

  val it:Iteratee[Int,Int] = {
    def step(state:Int)(in:Input[Int]):Iteratee[Int,Int] = in match{
      case Input.El(e) => {println(e); Cont(i => step(state + e)(i))}
      case Input.EOF => { Done(state, Input.EOF)}
    }
    Cont(i => step(0)(i))
  }

foldを導入することでここまでスッキリ書くことができるようになりました。

今回はここまで。Enimerator/Enumerateeについては後日（書けたら）書こうと思います。

最後に今回のコード全体を掲載しておきます。なんちゃってEnumeratorが実装されてますが、単にfoldLeftを実行するだけのものとなっています。

object MyIteratee{
  sealed trait Input[+E] {
  }

  object Input {
    case class El[+E](e: E) extends Input[E]
    case object EOF extends Input[Nothing]
  }

  trait Iteratee[E, A] {
    def fold[B](done:(A, Input[E]) => B,
		cont:(Input[E] => Iteratee[E,A]) => B): B

    def feed(in:Input[E]): Iteratee[E,A] =
      fold( (a,e) => Done(a,e),
	   k => k(in))

    def run():A =
      fold( (a, _) => a,
	   k => k(Input.EOF).fold( (a1, _) => a1,
				  _ => sys.error("diverging iteratee after Input.EOF")))
  }

  trait Enumerator[E]{
    def apply[A](i: Iteratee[E, A]): Iteratee[E, A]
    def |>>[A](i: Iteratee[E, A]): Iteratee[E, A] = apply(i)
  }

  object Enumerator{
    def apply[E](in: E*): Enumerator[E] = new Enumerator[E] {
      def apply[A](i: Iteratee[E, A]): Iteratee[E, A] = enumerate(in, i)
    }

    private def enumerate[E, A]: (Seq[E], Iteratee[E, A]) => Iteratee[E, A] = { (l, i) =>
      l.foldLeft(i)((it, e) => it.feed(Input.El(e)))
    }
  }

  object Cont{
    def apply[E, A](k: Input[E] => Iteratee[E, A]): Iteratee[E, A] = new Iteratee[E, A] {
      def fold[B](done: (A, Input[E]) => B,
		  cont: (Input[E] => Iteratee[E, A]) => B
		  ): B = cont(k)
    }
  }

  object Done {
    def apply[E, A](a: A, e: Input[E]): Iteratee[E, A] = new Iteratee[E, A] {
      def fold[B](done: (A, Input[E]) => B,
		  cont: (Input[E] => Iteratee[E, A]) => B): B = done(a, e)
    }
  }

}

object Main extends App{
  import MyIteratee._

  val it:Iteratee[Int,Int] = {
    def step(state:Int)(in:Input[Int]):Iteratee[Int,Int] = in match{
      case Input.El(e) => {println(e); Cont(i => step(state + e)(i))}
      case Input.EOF => { Done(state, Input.EOF)}
    }
    Cont(i => step(0)(i))
  }

  println ((Enumerator(1,2,3) |>> it).run())
}