Churchencoding of Cofree Terms

CofreeChurch.scala

  trait Expr[-I, +O] {
    def Lit: Int => O
    def Add: (I, I) => O
  }

  trait Term {
    def apply[R](alg: Expr[R, R]): R
  }

  trait AnnotTerm[A] {
    def apply[R](alg: Expr[R, A => R]): R
  }

  def annotate[A](t: Term, algA: Expr[A, A]): AnnotTerm[A] =
    t.apply(new Expr[(A, AnnotTerm[A]), (A, AnnotTerm[A])] {
      def Lit = n => {
        val a = algA.Lit(n)
        val t = new AnnotTerm[A] {
          def apply[R](alg: Expr[R, A => R]) = alg.Lit(n)(a)
        }
        (a, t)
      }
      def Add = (lhs, rhs) => {
        val a = algA.Add(lhs._1, rhs._1)
        val t = new AnnotTerm[A] {
          def apply[R](alg: Expr[R, A => R]) =
            alg.Add(lhs._2(alg), rhs._2(alg))(a)
        }
        (a, t)
      }
    })._2