MuFixEqLazy.scala

import cats.Eval
import cats.syntax.all._

trait Eq[A] {
  def eqv(x: A, y: A): Eval[Boolean]
}
trait Eq1[F[_]] {
  def eqv1[A](x: F[A], y: F[A])(implicit A: Eq[A]): Eval[Boolean]
}

final case class Fix[F[_]](unfix: Eval[F[Fix[F]]])
object Fix {
  implicit def eqv[F[_]: Eq1]: Eq[Fix[F]] = new Eq[Fix[F]] {
    override def eqv(x: Fix[F], y: Fix[F]): Eval[Boolean] = 
      (x.unfix product y.unfix).flatMap { case (x, y) =>
        implicitly[Eq1[F]].eqv1[Fix[F]](x, y)
      }
  }
}

trait Mu[F[_]] {
  def run[Z](f: Eval[F[Z]] => Z): Z
  def toFix: Fix[F] = run(fa => Fix[F](fa))
}

object Mu {
  implicit def eqv[F[_]: Eq1]: Eq[Mu[F]] = new Eq[Mu[F]] {
    def eqv(x: Mu[F], y: Mu[F]): Eval[Boolean] = 
      Fix.eqv.eqv(x.toFix, y.toFix)
  }
}

trait MuAlg[Alg[_]] {
  def run[Z](alg: Alg[Z]): Z
}

sealed trait ListF[+A, +L]
final case object NilF extends ListF[Nothing, Nothing]
final case class ConsF[H, T](head: H, tail: T) extends ListF[H, T]
object ListF {
  implicit def eq1[A](implicit A: Eq[A]): Eq1[ListF[A, ?]] = new Eq1[ListF[A, ?]] {
    def eqv1[L](x: ListF[A, L], y: ListF[A, L])(implicit L: Eq[L]): Eval[Boolean] =
      (x, y) match {
        case (NilF, NilF) => Eval.now(true)
        case (ConsF(h1, t1), ConsF(h2, t2)) => A.eqv(h1, h2).flatMap {
          case false => Eval.now(false)
          case true => L.eqv(t1, t2)
        }
      }
  }
}