package fps

import scala.language.higherKinds

object Free {

  sealed trait Free[F[_], A]

  case class Return[F[_], A](a: A) extends Free[F, A]

  case class Suspend[F[_], A](s: F[A]) extends Free[F, A]

  case class FlatMap[F[_], A, B](s: Free[F, A], f: A => Free[F, B]) extends Free[F, B]

  def freeMonad[F[_]]: Monad[Free[F, _]] =
    new Monad[({type f[x] = Free[F, x]})#f] {

      override def unit[A](a: => A): Free[F, A] = Return(a)

      override def flatMap[A, B](fa: Free[F, A])(f: A => Free[F, B]): Free[F, B] = fa flatMap f
    }

  @tailrec
  def runTrampoline[A](a: Free[Function0, A]): A = a match {
    case Return(a) => a
    case Suspend(r) => r()
    case FlatMap(x, f: (A => Free[Function0, A])) => x match {
      case Return(a: A) => runTrampoline(f(a))
      case Suspend(r) => runTrampoline(f(r()))
      case FlatMap(y: Free[Function0, A], g: (A => Free[Function0, A])) =>
        runTrampoline(y flatMap (a => g(a) flatMap f))
    }
  }
}