implementing_free.scala

import scalaz.{Free => _, _}, Scalaz._

object Attempt1 {

  sealed trait Free[S[_], A]
  case class Done[S[_], A](a: A) extends Free[S, A]
  case class Roll[S[_], A](k: S[Free[S, A]]) extends Free[S, A]

  object Free {

    implicit def monad[S[_] : Functor]: Monad[Free[S, ?]] =
      new Monad[Free[S, ?]] {

        def point[A](a: => A): Free[S, A] = Done(a)

        def bind[A, B](fa: Free[S, A])(f: A => Free[S, B]): Free[S, B] = {
          val func: Free[S, A] => Free[S, B] = bind[A, B](_)(f)

          fa match {
            case Done(a) => f(a)
            case Roll(k) => Roll[S, B](k.map(func))
          }
        }
      }

    def run[S[_] : Functor, A](fa: Free[S, A])(u: S[Free[S, A]] => Free[S, A]): A =
      fa match {
        case Done(a) => a
        case Roll(k) => u(k)
      }

  }
}

object Attempt2 {
  sealed trait Free[S[_], A]
  case class Done[S[_], A](a: A) extends Free[S, A]
  case class Roll[S[_], A](k: S[Free[S, A]]) extends Free[S, A]
  case class Bind[S[_], A, B](fa: Free[S, A], f: A => Free[S, B]) extends Free[S, B]

  object Free {

    implicit def monad[S[_] : Functor]: Monad[Free[S, ?]] =
      new Monad[Free[S, ?]] {

        def point[A](a: => A): Free[S, A] = Done(a)

        def bind[A, B](fa: Free[S, A])(f: A => Free[S, B]): Free[S, B] = {
          Bind[S, A, B](fa, f)
        }
      }

    def resume[S[_] : Functor, A](fa: Free[S, A]): S[Free[S, A]] \/ A = fa match {
      case Done(a) => a.right
      case Roll(k) => k.left
      case Bind(nfa, f) => nfa match {
        case Done(a) => resume(f(a))
        case Roll(k) => k.map(_.flatMap(f)).left
        case Bind(b, g) => resume(b.flatMap(g(_) flatMap f))
      }
    }

    def run[S[_] : Functor, A](fa: Free[S, A])(u: S[Free[S, A]] => Free[S, A]): A =
      resume(fa) match {
        case \/-(a) => a
        case -\/(k) => run(u(k))(u)
      }
  }


  type Trampoline[A] => Free[Function0, A]

  type Pair[A] = (A, A)

  type BinaryTree = Free[Pair, A]

}