church_encoding_maybe.scala

import scala.language.higherKinds
import scala.language.implicitConversions

trait Forall[M[_]] {
  def apply[A]: M[A]
}

trait Maybe[A] extends Forall[({ type F[R] = (A => R, => R) => R })#F]

object Maybe {

  implicit class ops[A](val m: Maybe[A]) extends AnyVal{
    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 Maybe[A]{
    def apply[R] = (f, r) => f(a)
  }

  def bind[A, B](f: A => Maybe[B])(m: Maybe[A]): Maybe[B] =
    new Maybe[B]{
      def apply[R] = (g, r) => m[R](a => f(a)[R](g, r), r)
    }

  def empty[A]: Maybe[A] =
    new Maybe[A]{
      def apply[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))
}