MonadFix.scala

package mf

import cats._
import cats.laws._

trait MonadFix[F[_]] extends Monad[F] {
  def mfix[A](f: Eval[A] => F[A]): F[A]
}

object MonadFix {

  implicit val mfOption: MonadFix[Option] = new MonadFix[Option] {
    def pure[A](a: A): Option[A] = Some(a)
    def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = fa flatMap f
    def mfix[A](f: Eval[A] => Option[A]): Option[A] = {
      def unjust(o: Option[A]): A = o.getOrElse(sys.error("empty"))
      lazy val x: Eval[Option[A]] = Eval.later(f(x.map(unjust)))
      x.value
    }
  }
}

trait MonadFixLaws[F[_]] extends MonadLaws[F] {
  implicit override def F: MonadFix[F]
}