blah.scala

type Unit = scala.Unit
object Unit {
  type K1[_] = Unit
  type K2[_, _] = Unit
  type KK1[_[_]] = Unit

  implicit val trivial: Unit = ()
}

type Nothing = scala.Nothing
object Nothing {
  type K1[_] = Nothing
  type K2[_, _] = Nothing
  type KK1[_[_]] = Nothing
}

trait Semigroupoid[F[_, _]] {
  def andThen[A, B, C](ab: F[A, B], bc: F[B, C]): F[A, C]
  def compose[A, B, C](bc: F[B, C], ab: F[A, B]): F[A, C] = andThen(ab, bc)
}

trait Category[F[_, _]] extends Semigroupoid[F] { f =>
  type C0[A]
  type C1[A, B] = F[A, B]
  def id[A](implicit A: C0[A]): F[A, A]
}
object Category {
  type Aux[C1[_, _], C0_[_]] = Category[C1] { type C0[A] = C0_[A] }
}

trait Groupoid[F[_, _]] extends Category[F] { f =>
  def flip[A, B](ab: F[A, B]): F[B, A]
}
object Groupoid {
  type Aux[C1[_, _], C0_[_]] = Groupoid[C1] { type C0[A] = C0_[A] }
}

trait SemigroupoidK[F[_[_], _[_]]] {
  def andThen[A[_], B[_], C[_]](ab: F[A, B], bc: F[B, C]): F[A, C]
  def compose[A[_], B[_], C[_]](bc: F[B, C], ab: F[A, B]): F[A, C] = andThen(ab, bc)
}

trait CategoryK[F[_[_], _[_]]] extends SemigroupoidK[F] { f =>
  type Obj[_[_]]
  def id[A[_]](implicit A: Obj[A]): F[A, A]
}
object CategoryK {
  type Aux[F[_[_], _[_]], O[_[_]]] = CategoryK[F] { type Obj[A[_]] = O[A] }
}

trait GroupoidK[F[_, _]] extends CategoryK[F] { f =>
  def flip[A[_], B[_]](ab: F[A, B]): F[B, A]
}
object GroupoidK {
  type Aux[F[_[_], _[_]], O[_[_]]] = GroupoidK[F] { type Obj[A[_]] = O[A] }
}

type ∀[F[_]] = Forall[F]
trait Forall[F[_]] { f =>
  def apply[A]: F[A]

  def mapK[G[_]](fg: F ~> G): ∀[G] = new ∀[G] {
    def apply[A]: G[A] = fg.apply(f.apply)
  }

  def lift[G[_]]: ∀[λ[X => F[G[X]]]] = new ∀[λ[X => F[G[X]]]] {
    def apply[A]: F[G[A]] = f.apply[G[A]]
  }
}

type ∃[F[_]] = Exists[F]
trait Exists[F[_]] { f =>
  type A
  def apply: F[A]

  def mapK[G[_]](fg: F ~> G): ∃[G] = new ∃[G] {
    type A = f.A
    def apply: G[f.A] = fg.apply(f.apply)
  }
}

object Function {
  def id[A]: A => A = (a: A) => a

  val category: Category.Aux[? => ?, Unit.K1] = new Category[? => ?] {
    type C0[A] = Unit.K1[A]
    def id[A](implicit A: C0[A]): A => A = Function.id
    def andThen[A, B, C](ab: A => B, bc: B => C): A => C = ab andThen bc
  }
}

type ~>[F[_], G[_]] = FunctionK[F, G]
trait FunctionK[F[_], G[_]] { fg =>
  def apply[A](fa: F[A]): G[A]

  def andThen[H[_]](gh: G ~> H): F ~> H = new (F ~> H) {
    def apply[A](fa: F[A]): H[A] = gh.apply(fg.apply(fa))
  }
  def compose[H[_]](hf: H ~> F): H ~> G = hf andThen fg
}
object FunctionK {
  def id[F[_]]: F ~> F = new (F ~> F) {
    def apply[A](fa: F[A]): F[A] = fa
  }

  val category: CategoryK.Aux[? ~> ?, Unit.KK1] = new CategoryK[? ~> ?] {
    type Obj[A[_]] = Unit.KK1[A]
    def id[A[_]](implicit A: Obj[A]): A ~> A = FunctionK.id
    def andThen[A[_], B[_], C[_]](ab: A ~> B, bc: B ~> C): A ~> C = ab andThen bc
  }
}

type ===[A, B] = Leibniz[A, B]
trait Leibniz[A, B] { ab =>
  def apply[F[_]](fa: F[A]): F[B]

  def andThen[C](bc: B === C): A === C = new (A === C) {
    def apply[F[_]](fa: F[A]): F[C] = bc.apply(ab.apply(fa))
  }
  def compose[C](ca: C === A): C === B = ca andThen ab

  def flip: B === A =
    apply[? === A](Leibniz.id)
  def lift[F[_]]: F[A] === F[B] =
    apply[λ[X => F[A] === F[X]]](Leibniz.id)
  def coerce(a: A): B =
    apply[λ[X => X]](a)
}
object Leibniz {
  def id[A]: A === A = new (A === A) {
    def apply[F[_]](fa: F[A]): F[A] = fa
  }

  val groupoid: Groupoid.Aux[? === ?, Unit.K1] = new Groupoid[? === ?] {
    type C0[A] = Unit.K1[A]
    def id[A](implicit A: C0[A]): A === A = Leibniz.id
    def andThen[A, B, C](ab: A === B, bc: B === C): A === C = ab andThen bc
    def flip[A, B](ab: A === B): B === A = ab.flip
  }
}

trait Functor[F[_]] { f =>
  type C0[_]
  type C1[_, _]
  def C: Category.Aux[C1, C0]

  type D0[_]
  type D1[_, _]
  def D: Category.Aux[D1, D0]

  def map[A, B](ab: C1[A, B]): D1[F[A], F[B]]

  def andThen[G[_]](g: Functor[G]): Functor[λ[X => G[F[X]]]] = new Functor[λ[X => G[F[X]]]] {
    override def map[A, B](ab: A => B): G[F[A]] => G[F[B]] = g.map[F[A], F[B]](f.map[A, B](ab))
  }
  def compose[G[_]](g: Functor[G]): Functor[λ[X => F[G[X]]]] = g andThen f
}
object Functor {
  type Aux[C1_[_, _], C0_[_]]

  val id: Functor[λ[X => X]] = new Functor[λ[X => X]] {
    type C0[A] = Unit.K1[A]
    type C1[_, _]
    def C: Category.Aux[C1, C0]

    type D0[_]
    type D1[_, _]
    def D: Category.Aux[D1, D0]

    def map[A, B](ab: A => B): A => B = ab
  }
}