Free Free.scala

sealed trait Free[+F[_], A]
object Free {
  def eval[F[_], A](fa: Free[F, A])(implicit F: Monad[F]): F[A] = {
    type State = (Free[F, Any], List[Any => Free[F, Any]])
    def go(s: State): F[Either[State, Any]] = s match {
      case (current, stack) =>
        current match {
          case Done(a) => 
            stack match {
              case Nil     => 
                F.pure(Right(a))
              case f :: fs => 
                F.pure(Left(f(a) -> fs))
            }
          case current: Suspend[F, a] =>
            stack match {
              case Nil =>
                F.map(current.fa)(a => Right(a))
              case f :: fs =>
                F.map(current.fa)(a => Left(f(a) -> fs))
            }
          case current: FlatMap[F, a, b] =>
            F.pure(Left(current.fa.asInstanceOf[Free[F, Any]] -> (current.f.asInstanceOf[Any => Free[F, Any]] :: stack)))
        }
    }
    
    F.tailRecM((fa.asInstanceOf[Free[F, Any]], Nil) : State)(go _).asInstanceOf[F[A]]
  }
  
  final case class Done[A](a: A) extends Free[Nothing, A]
  final case class Suspend[F[_], A](fa: F[A]) extends Free[F, A]
  final case class FlatMap[F[_], A, B](fa: Free[F, A], f: A => Free[F, B]) extends Free[F, B]
  
  def pure[F[_], A](a: A): Free[F, A] = Done(a)
  def roll[F[_], A](fa: F[Free[F, A]]): Free[F, A] = 
    FlatMap[F, Free[F, A], A](Suspend(fa), x => x)
}