matryoshka.scala

package matryoshka {
  trait Interpret[T[_[_]]] {
    type ^[Outer[_], Inner[_]] = Outer[T[Inner]]

    trait Transform[F[_], G[_]] {
      /** Bottom-up transforms. */
      type GAlgebraicM[W[_], M[_]]   = F[W ^ G] => M[G ^ G]
      type AlgebraicM[M[_]]          = F   ^ G  => M[G ^ G] // GAlgebraicM[Id, M]
      type GAlgebraic[W[_]]          = F[W ^ G] =>   G ^ G  // GAlgebraicM[W, Id]
      type Algebraic                 = F   ^ G  =>   G ^ G  // GAlgebraicM[Id, Id]

      /** Top-down transforms. */
      type GCoalgebraicM[N[_], M[_]] = F ^ F => M[G[N ^ F]]
      type CoalgebraicM[M[_]]        = F ^ F => M[G   ^ F ]  // GCoalgebraicM[Id, M]
      type GCoalgebraic[N[_]]        = F ^ F =>   G[N ^ F]   // GCoalgebraicM[N, Id]
      type Coalgebraic               = F ^ F =>   G   ^ F    // GCoalgebraicM[Id, Id]
    }
  }
}