import cats.~>

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

trait Monad[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

  def map[A, B](fa: F[A])(f: A => B): F[B] =
    flatMap(fa)(a => pure(f(a)))
}

trait FreeMonad[Free[_[_], _]] {
  def instance[F[_]]: Monad[Free[F, ?]]
  def foldMap[F[_], G[_]: Monad](f: F ~> G): Free[F, ?] ~> G
}

trait MonadError[E, F[_]] {
  def pure[A](a: A): F[A]
  def raiseError[A](e: E): F[A]
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def handleWith[A, B](fa: F[A])(f: E => F[A]): F[A]
}

trait FreeMonadError[Free[_, _[_], _]] {
  def instance[E, F[_]]: MonadError[E, Free[E, F, ?]]
  def foldMap[E, F[_], EE, G[_]](f: F ~> G, g: E => EE)(implicit G: MonadError[EE, G]): Free[E, F, ?] ~> G
}

trait Comonad[F[_]] extends Functor[F] {
  def extract[A](fa: F[A]): A
  def coflatMap[A, B](fa: F[A])(f: F[A] => B): F[B]
  def map[A, B](fa: F[A])(f: A => B): F[B] = coflatMap(fa)(fa => f(extract(fa)))
  def duplicate[A](fa: F[A]): F[F[A]] = coflatMap(fa)(identity)
}

trait FreeComonad[Free[_[_], _]] {
  def instance[F[_]: Functor]: Comonad[Free[F, ?]]
  def extract[E, F[_]: Functor]: Free[F, ?] ~> F
  def cofoldMap[F[_]: Functor, G[_]: Comonad, A](ga: G[A])(f: G ~> F): Free[F, A]
}

final case class Cofree[S[_], A](head: A, tail: S[Cofree[S, A]])

val cofree: FreeComonad[Cofree] = new FreeComonad[Cofree] {
  def instance[F[_]](implicit F: Functor[F]): Comonad[Cofree[F, ?]] = new Comonad[Cofree[F, ?]] {
    def extract[A](fa: Cofree[F, A]): A = fa.head

    def coflatMap[A, B](fa: Cofree[F, A])(f: Cofree[F, A] => B): Cofree[F, B] =
      Cofree[F, B](f(fa), F.map(fa.tail)(coflatMap(_)(f)))
  }

  def extract[E, F[_]](implicit F: Functor[F]): Cofree[F, ?] ~> F = new (Cofree[F, ?] ~> F) {
    def apply[A](fa: Cofree[F, A]): F[A] = F.map(fa.tail)(instance[F].extract)
  }

  def cofoldMap[F[_], G[_], A](ga: G[A])(f: G ~> F)(implicit F: Functor[F], G: Comonad[G]): Cofree[F, A] =
    Cofree(G.extract(ga), F.map(f(G.duplicate(ga)))(cofoldMap(_)(f)))
}

trait Eq[A] {
  def equal(a: A, b: A): Boolean
}
trait FreeEq[Free[_]] {
  def instance[A]: Eq[Free[A]]
  def cofoldMap[A, B: Eq](f: B => A): B => Free[A]
}