Relating fixed points with pattern functors

fixpoint.scala

package object fixpoint {

  // The idea here is similar (though inverted) to Matryoschka Based: 
  //   https://github.com/slamdata/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Based.scala
  trait Fix[F[_]] {
    type Out
    def roll: F[Out] => Out
    def unroll: Out => F[Out]
  }
  trait Functor[F[_]] {
    def map[A, B](f: A => B): F[A] => F[B]
  }

  object morphisms {
    def cata[F[_]: Functor, R](alg: F[R] => R)(implicit fix: Fix[F]): fix.Out => R = x => 
      alg(implicitly[Functor[F]].map(cata(alg))(fix.unroll(x)))
  }

  object pattern {
    trait ExprF[X]
    case class Lit[X](n: Int) extends ExprF[X]
    case class Add[X](l: X, r: X) extends ExprF[X]
    object ExprF {
      implicit object fixpoint extends Fix[ExprF] {
        type Out = fix.Expr
        def roll = {
          case Lit(n) => fix.Lit(n)
          case Add(l, r) => fix.Add(l, r)
        }
        def unroll = {
          case fix.Lit(n) => Lit(n)
          case fix.Add(l, r) => Add(l, r)
        }
      }
      implicit object functor extends Functor[ExprF] {
        def map[A, B](f: A => B) = {
          case Lit(n) => Lit(n)
          case Add(l, r) => Add(f(l), f(r))
        }
      }
    }

    val eval: ExprF[Int] => Int = {
      case Lit(n) => n
      case Add(l, r) => l + r
    }
  }
  object fix {
    trait Expr
    case class Lit(n: Int) extends Expr
    case class Add(l: Expr, r: Expr) extends Expr

    val tree = Add(Add(Lit(1), Lit(2)), Add(Lit(3), Lit(4)))

    morphisms.cata(pattern.eval).apply(tree)
  }

}