ScalaでChurch encoding

data Maybe a = Nothing | Just a
という型をekmettさんのコードを参考にChurch encodingしてみると、

newtype Maybe { runMaybe :: forall r. a -> r -> r -> r }

となります。（多分）

これをScalaで表現してみました。

	import scala.language.higherKinds
	import scala.language.implicitConversions
	import scala.language.reflectiveCalls
	trait Forall[M[_]] {
	def apply[A]: M[A]
	}
	object Maybe {
	type Maybe[A] = Forall[({ type F[R] = (A => R, => R) => R })#F]
	implicit def ops[A](m: Maybe[A]) = new {
	def map[B](f: A => B): Maybe[B] = bind(point[B]_ compose f)(m)
	def flatMap[B](f: A => Maybe[B]): Maybe[B] = bind(f)(m)
	}
	def point[A](a: A): Maybe[A] =
	new Forall[({ type F[R] = (A => R, => R) => R })#F] {
	def apply[R]: (A => R, => R) => R = (f, r) => f(a)
	}
	def bind[A, B](f: A => Maybe[B])(m: Maybe[A]): Maybe[B] =
	new Forall[({ type F[R] = (B => R, => R) => R })#F] {
	def apply[R]: (B => R, => R) => R =
	(g, r) => m[R](a => f(a)[R](g, r), r)
	}
	def empty[A]: Maybe[A] =
	new Forall[({ type F[R] = (A => R, => R) => R })#F] {
	def apply[R]: (A => R, => R) => R = (f, r) => r
	}
	def run[A](a: A)(m: Maybe[A]): A = m[A](x => x, a)
	}
	object Main extends App {
	import Maybe._
	def get[K, V](k: K)(m: Map[K, V]): Maybe[V] =
	m get k map point[V] getOrElse empty[V]
	val foobar = Map('foo -> 2, 'bar -> 3)
	println(run(-1)(for {
	m <- get('foo)(foobar)
	n <- get('bar)(foobar)
	} yield m + n))
	println(run(-1)(for {
	m <- get('baz)(foobar)
	n <- get('bar)(foobar)
	} yield m + n))
	}

view raw gistfile1.scala hosted with ❤ by GitHub

とても面倒なことになってますが、ちゃんとMaybeモナドとして動作します。
Haskellだと結構綺麗に書けたりします。

Church encodingすると大抵の場合に高速化されます。
このMaybeモナドの例では、emptyをbindで合成した時に、Justの場合の処理を破棄しています。

ラムダ計算で代数的データ型を表現する方法

この記事も面白いのでぜひ読んでみて下さい。