Church encoding of Option

README.md

Regular Option

sealed trait Option[+A]
case class Some[+A](a: A) extends Option[A]
case object None extends Option[Nothing]

implicit def optionMonad[A](o: Option[A]) =
  new MonadOps[A] {
    def flatMap[B](f: A => Option[B]) = o match {
      case None => None
      case Some(x) => f(x)
    }
    def map[B](f: A => B) = flatMap(f andThen Some)
  }

Church encoding of Option

// type OptionC[A] = forall B. B => (A => B) => B
trait OptionC[+A] {
  def mk[B]: B => (A => B) =>B
}

def some[A](a: A) = new OptionC[A] { def mk[B] = n => s => s(a) }
def none[A]       = new OptionC[A] { def mk[B] = n => _ => n }

implicit def optionCMonad[A](option: Maybe[A]) =
  new MonadOps[Maybe, A] {
    def flatMap[B](f: A => Maybe[B]) =
      new Maybe[B] {
        def mk[B] = n => s => {
          option.mk(n) { a => f(a).mk(n)(s) }
        }
      }
    def map[B](f: A => B): Maybe[B] = flatMap(f andThen some)
  }

Usage

Add 1 and 2.

> val x = for (a <- some(1); b <- some(2)) yield a + b
> x.mk()(println)
3

Short circuit on none.

> val y = for (a <- none[Int]; b <- some(2)) yield a + b
> x.mk(println("nothing"))(println)
nothing