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

trait Monad[F[_]] extends Functor[F] {
  def point[A](a: A): F[A]
  def bind[A, B](f: A => F[B])(F: F[A]): F[B]
  def fmap[A, B](f: A => B)(F: F[A]): F[B] =
    bind((a: A) => point(f(a)))(F)
}

abstract class Free[F[_]: Functor, A]
case class Done[F[_]: Functor, A](a: A) extends Free[F, A]
case class More[F[_]: Functor, A](fa: F[Free[F, A]]) extends Free[F, A]

object Syntax {
  implicit class FunctorSyntax[F[_], A](fa: F[A])(implicit F: Functor[F]) {
    def fmap[B](f: A => B): F[B] = F.fmap(f)(fa)
    def map[B](f: A => B): F[B] = fmap(f)
  }

  implicit class MonadSyntax[F[_], A](fa: F[A])(implicit F: Monad[F]) {
    def bind[B](f: A => F[B]): F[B] = F.bind(f)(fa)
    def flatMap[B](f: A => F[B]): F[B] = bind(f)
  }
}

object Instances {
  import Syntax._

  implicit def FreeMonad[F[_]: Functor] = new Monad[({type λ[a] = Free[F, a]})#λ] {
    def point[A](a: A): Free[F, A] = Done(a)
    def bind[A, B](f: A => Free[F, B])(Fa: Free[F, A]): Free[F, B] =
      Fa match {
        case Done(a)  => f(a)
        case More(fa) => More(fa fmap (free => bind(f)(free)))
      }
  }
}

object Algebra {
  sealed trait Operation[A]
  case class Addition[A](lhs: Int, rhs: Int, a: Int => A) extends Operation[A]
  case class Subtraction[A](lhs: Int, rhs: Int, a: Int => A) extends Operation[A]

  implicit val OperationFunctor = new Functor[Operation] {
    def fmap[A, B](f: A => B)(F: Operation[A]): Operation[B] =
      F match {
        case Addition(lhs, rhs, a)    => Addition(lhs, rhs, x => f(a(x)))
        case Subtraction(lhs, rhs, a) => Subtraction(lhs, rhs, x => f(a(x)))
      }
  }

  object Operation {
    def add(lhs: Int, rhs: Int): Free[Operation, Int] =
      More(Addition(lhs, rhs, res => Done(res)))

    def sub(lhs: Int, rhs: Int): Free[Operation, Int] =
      More(Subtraction(lhs, rhs, res => Done(res)))

    def run[A](operation: Free[Operation, A]): A =
      operation match {
        case Done(result)                   => result
        case More(Addition(lhs, rhs, f))    => run(f(lhs + rhs))
        case More(Subtraction(lhs, rhs, f)) => run(f(lhs - rhs))
      }
  }

  def example: Unit = {
    import Operation._
    import Instances._
    import Syntax._

    val operations = for {
      x1 <- add(4, 4)
      x2 <- add(3, 3)
      x3 <- sub(x1, x2)
    } yield x3

    println(run(operations))
  }
}