Partially applied "type constructors" in Scala

partial.scala

// 1. Instead of using type parameters, we use type members
trait Expr {
  type ExprIn
  type ExprOut
  type Base[+_]
}

trait Monadic {
  type M[+_]
}

trait Rep[+_]

// type restrictions, value based
trait TR[E <: Expr] {
  type Out = E
  def base[B[+_]]: TR[E { type Base[+A] = B[A] }] = ???
  def in[T]: TR[E { type ExprIn = T }]
  def out[T]: TR[E { type ExprOut = T }]
}

val c = TR[Expr].base[Rep].in[Int].out[String]
type E = c.Out

implicitly[E <:< Expr {
  type Base[+A] = Rep[A]
  type ExprIn = Int
  type ExprOut = String
}]

// type restrictions, only type based
trait TR2[E <: Expr] {
  type Out = E
  type staged = TR2[Out { type Base[+A] = Rep[A] }]
  type base[B[+_]] = TR2[Out { type Base[+A] = B[A] }]
  type alg[T] = TR2[Out { type ExprIn = T; type ExprOut = T }]
  type in[T] = TR2[Out { type ExprIn = T }]
  type out[T] = TR2[Out { type ExprOut = T }]
  type monadic[M0[+_]] = TRM[Out with Monadic { type M[+A] = M0[A]} ]
}

trait TRM[E <: Expr with Monadic] {
  type Out = E
  type m[M0[+_]] = TRM[Out { type M[+A] = M0[A] }]
  type alg[T] = TR2[Out { type ExprIn = Out#M[T]; type ExprOut = Out#M[T] }]
  type in[T] = TR2[Out { type ExprIn = Out#M[T] }]
  type out[T] = TR2[Out { type ExprOut = Out#M[T] }]
}

type E2 = TR2[Expr]
  # base[Rep]
  # alg[Int]
  # monadic [List]
  # Out

implicitly[E2 <:< Expr with Monadic {
  type Base[+A] = Rep[A]
  type ExprIn = Int
  type ExprOut = Int
  type M[+A] = List[A]
}]

type E3 = TR2[Expr]
  # staged
  # monadic [List]
  # alg [Int]
  # Out

implicitly[E3 <:< Expr with Monadic {
  type Base[+A] = Rep[A]
  type ExprIn = List[Int]
  type ExprOut = List[Int]
  type M[+A] = List[A]
}]