Codensity

この記事はScalaz Advent Calendarの13日目の記事です。

Codensityについてググると、

The Mother of all Monads

という記事が見つかる。
Codensityは継続モナドとほぼ同じものみたい。

この記事にある例をScalaで書いてみる。

	def i[F[+_]: Monad, A](a: F[A]) = new Codensity[F, A] {
	def apply[B](f: A => F[B]) = a >>= f
	}

view raw i.scala hosted with ❤ by GitHub

Option

	val map = Map('foo -> "bar", 'hoge -> "fuga")
	(for {
	x <- i(map get 'foo)
	y <- i(map get 'hoge)
	} yield x + y).improve assert_=== Some("barfuga")

view raw option.scala hosted with ❤ by GitHub

Disjunction

	type StrDisj[+A] = String \/ A
	(for {
	x <- i[StrDisj, String]((map get 'foo) \/> "foo")
	y <- i[StrDisj, String]((map get 'baz) \/> "baz")
	} yield x + y).improve assert_=== "baz".left

view raw disj.scala hosted with ❤ by GitHub

なるほど。
CodensityがOptionやDisjunctionとして動く。

でもこれってIdTじゃ(ry

Codensityは継続モナドのようなもの、ということで継続らしい例を書いてみる。

iprintで、計算の経過を表示する。

	def iprint[F[+_]: Monad, A](a: F[A]) = new Codensity[F, A] {
	def apply[B](f: A => F[B]) = {
	println(a)
	a >>= f
	}
	}
	(for {
	x <- iprint(map get 'foo)
	y <- iprint(map get 'baz)
	} yield x + y).improve assert_=== None

view raw iprint.scala hosted with ❤ by GitHub

Some(bar)とNoneが表示される。

継続を破棄するbreakを定義し、for式で使ってみる。

	def break[F[+_]: PlusEmpty, A] = new Codensity[F, A] {
	def apply[B](f: A => F[B]) = PlusEmpty[F].empty[B]
	}
	(for {
	x <- iprint(map get 'foo)
	_ <- break[Option, String]
	y <- iprint(map get 'hoge)
	} yield x + y).improve assert_=== None

view raw break.scala hosted with ❤ by GitHub

Some(bar)だけが表示される。

無事、計算が破棄された。

Codensityはあるモナドにおいて計算量を減らせることがわかった。
他にも何か出来そうだが、わたしが思いついたのはこれくらい。