Scala Type Level Programming: The Natural Numbers: Exponentiation

type-level-programming-natural-numbers-exponentiation.scala

sealed trait Nat {
  type exp[That <: Nat] <: Nat
  type expflip[That <: Nat] <: Nat
}

sealed trait MsbZero extends Nat {
  override type exp[That <: Nat] = MsbZero
  override type expflip[That <: Nat] = MsbOne
}

sealed trait MsbOne extends Nat {
  override type exp[That <: Nat] = MsbOne
  override type expflip[That <: Nat] = That
}

sealed trait B0[HigherBits <: Nat] extends Nat {
  override type exp[That <: Nat] = That#expflip[B0[HigherBits]]
  override type expflip[That <: Nat] = HigherBits#expflip[That#mult[That]]
}

sealed trait B1[HigherBits <: Nat] extends Nat {
  override type exp[That <: Nat] = That#expflip[B1[HigherBits]]
  override type expflip[That <: Nat] = HigherBits#expflip[That#mult[That]]#mult[That]
}