ScalazでIteratee

Scala会議でLTしてきました。

Scalaz effects

View more presentations from Sanshiro Yoshida

拙い発表でしたが、まじめに聞いてくれたScala会議参加者の方々には感謝です。
このLTで話せなかったIterateeについて、tanakhさんのブログを参考に書かせていただきます。

Scalazでの実装

ブログを参考に実際に実装してみます。

	sealed trait StreamG[+E]
	case object Empty extends StreamG[Nothing]
	case class El[E](el: E) extends StreamG[E]
	case object EOF extends StreamG[Nothing]
	sealed trait IterV[+E, +A]
	case class Done[E, A](x: A, str: StreamG[E]) extends IterV[E, A]
	case class Cont[E, A](k: StreamG[E] => IterV[E, A]) extends IterV[E, A]

view raw a.scala hosted with ❤ by GitHub

定義は簡単。
Haskellのコードとあまり変わりがないですね。（ぇ
ストリームはList(El(1), El(2), El(3), EOF())みたいなイメージです。

	def enum[E, A]: (IterV[E, A], List[E]) => IterV[E, A] = {
	case (i, Nil) => i
	case (i@Done(_, _), _) => i
	case (Cont(k), x :: xs) => enum(k(El(x)), xs)
	}
	def run[E, A]: IterV[E, A] => Option[A] = {
	case Done(x, _) => Some(x)
	case Cont(k) => k(EOF) match {
	case Done(x, _) => Some(x)
	case _ => None
	}
	}

view raw b.scala hosted with ❤ by GitHub

enum,runの実装。
enumはfoldl（むしろreduce？)そのままで、IterVを関数と初期値にみたたて、Doneの場合でも結果を返すものと思えばいいです。
runは結果を取り出すだけ。初期値に当たるものがない場合があるので、結果はOptionで返します。

	def head[E]: IterV[E, Option[E]] = {
	def step: StreamG[E] => IterV[E, Option[E]] = {
	case El(el) => Done(Some(el), Empty)
	case Empty => Cont(step)
	case EOF => Done(None, EOF)
	}
	Cont(step)
	}
	def peek[E]: IterV[E, Option[E]] = {
	def step: StreamG[E] => IterV[E, Option[E]] = {
	case c@El(el) => Done(Some(el), c)
	case Empty => Cont(step)
	case EOF => Done(None, EOF)
	}
	Cont(step)
	}
	def drop[E]: Int => IterV[E, Unit] = {
	case 0 => Done((), Empty)
	case n => {
	def step: StreamG[E] => IterV[E, Unit] = {
	case El(_) => drop(n - 1)
	case Empty => Cont(step)
	case EOF => Done((), EOF)
	}
	Cont(step)
	}
	}
	def length[E]: IterV[E, Int] = {
	def step: (Int, StreamG[E]) => IterV[E, Int] = {
	case (acc, El(_)) => Cont(step.curried(acc + 1))
	case (acc, Empty) => Cont(step.curried(acc))
	case (acc, EOF) => Done(acc, EOF)
	}
	Cont(step.curried(0))
	}

view raw c.scala hosted with ❤ by GitHub

Iterateeたち。
これらをストリームに適用し、結果を得ます。curriedとか初めて使った気がします。
型が消えてしまうので、match式のところはwarningがいっぱいです。
この対処法がないのが残念なところ。（あったら教えてください

	implicit def IterVMonad[E] = new Monad[({type X[A] = IterV[E, A]})#X] {
	def pure[A](x: => A): IterV[E, A] = Done(x, Empty)
	def bind[A, B](m: IterV[E, A], f: A => IterV[E, B]): IterV[E, B] = m match {
	case Done(x, str) => f(x) match {
	case Done(x, _) => Done(x, str)
	case Cont(k) => k(str)
	}
	case Cont(k) => Cont((str: StreamG[E]) => bind(k(str), f))
	}
	}

view raw d.scala hosted with ❤ by GitHub

モナド。
PartialApplyを使おうとして嵌りました。定義のところで使っちゃダメなんですね・・・・
このインスタンスを作ることで、合成（>>=や>|>）を使うことができます。
Haskellと違って、Monadを定義すればFunctorやApplicativeがついてくるのでちょっと楽。

実行例

	def f[E](l: List[E]) = run(enum(drop(2) >|> length, l))
	f(List(1, 2, 3)) assert_=== Some(1)
	f(List(1, 2, 3, 4, 5)) assert_=== Some(3)
	f(List(1)) assert_=== Some(0)

view raw e.scala hosted with ❤ by GitHub

Haskellのコードそのままに書けるのは感動ですね。
次はIOを実装しようと思います。
kaitennさんにforkしてもらいました。