trait ~>[F[_], G[_]] {
  def apply[A]: F[A] => G[A]
}

case class Id[A](x: A)

trait Semigroup[M] {
  def op: M => M => M
}

trait Monoid[M] extends Semigroup[M] {
  val id: M
}

trait Functor[F[_]] {
  def fmap[A, B](f: A => B): F[A] => F[B]
}

trait Profunctor[=>:[_, _]]  {
  def mapfst[A, B, C](fab: (A =>: B))(f: C => A): (C =>: B)
  def mapsnd[A, B, C](fab: (A =>: B))(f: B => C): (A =>: C)
}

trait Apply[F[_]] extends Functor[F] {
  def ap[A, B](f: F[A => B]): F[A] => F[B]
}

trait Bind[F[_]] extends Apply[F] {
  def bind[A, B](f: A => F[B]): F[A] => F[B]
}

trait Applicative[F[_]] extends Apply[F] {
  def insert[A]: A => F[A]
}

trait Monad[F[_]] extends Applicative[F] with Bind[F]

trait Extend[F[_]] extends Functor[F] {
  def extend[A, B](f: F[A] => B): F[A] => F[B]
}

trait Comonad[F[_]] extends Extend[F] {
  def extract[A]: F[A] => A
}

trait ComonadApply[F[_]] extends Comonad[F] with Apply[F]

trait Plus[F[_]] extends Apply[F] {
  def plus[A]: F[A] => F[A] => F[A]
}

trait Alternative[F[_]] extends Plus[F] with Applicative[F] {
  def empty[A]: F[A]
}

trait BindPlus[F[_]] extends Plus[F] with Bind[F]

trait MonadPlus[F[_]] extends BindPlus[F] with Alternative[F] with Monad[F]

trait Contravariant[F[_]] {
  def contramap[A, B](f: B => A): F[A] => F[B]
}

trait Distributive[T[_]] extends Functor[T] {
  def distribute[F[_]: Functor, A, B](f: A => T[B]): F[A] => T[F[B]]
}

trait Fold[T[_]] {
  def foldMap[A, M: Monoid](f: A => M): T[A] => M
}

trait Fold1[T[_]] extends Fold[T] {
  def foldMap1[A, M: Semigroup](f: A => M): T[A] => M
}

trait Traverse[T[_]] extends Functor[T] with Fold[T] {
  def traverse[F[_]: Applicative, A, B](f: A => F[B]): T[A] => F[T[B]]
}

trait Traverse1[T[_]] extends Traverse[T] with Fold1[T] {
  def traverse1[F[_]: Apply, A, B](f: A => F[B]): T[A] => F[T[B]]
}

trait MonadTransformer[T[_[_], _]] {
  def lift[M[_]: Monad, A]: M[A] => T[M, A]
}

trait BindTransformer[T[_[_], _]] extends MonadTransformer[T] {
  def liftB[M[_]: Bind, A]: M[A] => T[M, A]
}

trait MonadTransform[T[_[_], _]] {
  def transform[F[_]: Monad, G[_]: Monad, A](f: F ~> G): T[F, A] => T[G, A]
}

trait BindTransform[T[_[_], _]] extends MonadTransform[T] {
  def transformB[F[_]: Bind, G[_]: Monad, A](f: F ~> G): T[F, A] => T[G, A]
}

trait ComonadTransformer[T[_[_], _]] {
  def lower[M[_]: Comonad, A]: T[M, A] => M[A]
}

trait ExtendTransformer[T[_[_], _]] extends ComonadTransformer[T] {
  def lowerE[M[_]: Extend, A]: T[M, A] => M[A]
}

trait ComonadHoist[T[_[_], _]] {
  def cohoist[M[_]: Comonad, A]: T[M, A] => T[Id, A]
}

trait ExtendHoist[T[_[_], _]] extends ComonadHoist[T] {
  def cohoistE[M[_]: Extend, A]: T[M, A] => T[Id, A]
}

trait Semigroupoid[~>[_, _]] {
  def compose[A, B, C]: (B ~> C) => (A ~> B) => (A ~> C)
}

trait Category[~>[_, _]] extends Semigroupoid[~>] {
  def id[A]: A ~> A
}

trait First[~>[_, _]] extends Semigroupoid[~>] {
  def first[A, B, C]: (A ~> B) => ((A, C) ~> (B, C))
}

trait Arrow[~>[_, _]] extends Category[~>] with First[~>] {
  def idA[A, B]: (A => B) => (A ~> B)
}