step1.scala

// Implementing functor manually

import scalaz._, Scalaz._, Free.liftF

sealed trait TestF[+A]
case class Foo[A](o: A) extends TestF[A]
case class Bar[A](h: (Int => A)) extends TestF[A]
case class Baz[A](h: (Int => A)) extends TestF[A]

implicit def testFFunctor[B]: Functor[TestF] = new Functor[TestF] {
  def map[A,B](fa: TestF[A])(f: A => B): TestF[B] = 
    fa match {
      case Foo(o) => Foo(f(o))
      case Bar(h) => Bar(x => f(h(x)))
      case Baz(h) => Baz(x => f(h(x)))
    }
}  

type TestFreeM[A] = Free[TestF, A]

def foo: TestFreeM[Unit] = liftF { Foo(Unit) }
def bar: TestFreeM[Int] = liftF { Bar(a => a) }
def baz: TestFreeM[Int] = liftF { Baz(a => a) }

def run[A](program: TestFreeM[A]): A = {
  val exe: TestF ~> Id = new (TestF ~> Id) {
    def apply[B](l: TestF[B]): B = l match { 
      case Foo(o) => { println(l); o }
      case Bar(h) => { println(l); h(42)}
      case Baz(h) => { println(l); h(20)}
    }
  }
  program.runM(exe.apply[TestFreeM[A]])
}

val program = for {
  _ <- foo
  a <- bar
  b <- baz
  _ <- foo
} yield (a, b)

run(program)

step2a.scala

// Implementing functor manually + EitherT

import scalaz._, Scalaz._, Free.liftF

sealed trait TestF[+A]
case class Foo[A](o: A) extends TestF[A]
case class Bar[A](h: (\/[String, Int] => A)) extends TestF[A]
case class Baz[A](h: (\/[String, Int] => A)) extends TestF[A]

implicit def testFFunctor[B]: Functor[TestF] = new Functor[TestF] {
  def map[A,B](fa: TestF[A])(f: A => B): TestF[B] = 
    fa match {
      case Foo(o) => Foo(f(o))
      case Bar(h) => Bar(x => f(h(x)))
      case Baz(h) => Baz(x => f(h(x)))
    }
}  

type TestFreeM[A] = Free[TestF, A]
type TestM[A] = EitherT[TestFreeM, String, A]

def foo = EitherT.right[TestFreeM, String, Unit] { liftF { Foo(Unit) } }
def bar = EitherT[TestFreeM, String, Int] { liftF { Bar(a => a) } }
def baz = EitherT[TestFreeM, String, Int] { liftF { Baz(a => a) } }

def run[A](program: TestFreeM[A]): A = {
  val exe: TestF ~> Id = new (TestF ~> Id) {
    def apply[B](l: TestF[B]): B = l match { 
      case Foo(o) => { println(l); o }
      case Bar(h) => { println(l); h(42.right)}
      case Baz(h) => { println(l); h("Baz called".left)}
    }
  }
  program.runM(exe.apply[TestFreeM[A]])
}

val program = for {
  _ <- foo
  a <- bar
  b <- baz
  _ <- foo
} yield (a, b)

val resultA = run(program.run)

step2b.scala

// Using Coyoneda to generate the map (without EitherT)

import scalaz._
import scalaz.syntax.functor._
import scalaz.effect._

sealed trait TestF[A]
case object Foo extends TestF[Unit]
case object Bar extends TestF[Int]
case object Baz extends TestF[Int]

type TestCoyo[A] = Coyoneda[TestF, A]
type TestFreeM[A] = Free.FreeC[TestF, A]

def foo = Free.liftFC(Foo)
def bar = Free.liftFC(Bar)
def baz = Free.liftFC(Baz)

def run[A, M[_]: Monad](tio: TestFreeM[A])(interpreter: TestF ~> M): M[A] = tio.foldMap[M](new (TestCoyo ~> M) {
  def apply[A](cy: TestCoyo[A]): M[A] =
    interpreter(cy.fi).map(cy.k)
})

def testToIO: TestF ~> IO = new (TestF ~> IO) {
  def apply[A](t: TestF[A]): IO[A] = t match {
    case Foo          => IO { println(t) }
    case Bar          => IO { println(t); 42 }
    case Baz          => IO { println(t); 20 }
  }
}

val program = for {
  _ <- foo
  a <- bar
  b <- baz
  _ <- foo
} yield (a, b)

val result = run(program)(testToIO)
result.unsafePerformIO

step3.scala

// TODO: Using EitherT+Coyoneda? Profit

import scalaz._, Scalaz._
import scalaz.syntax.functor._
import scalaz.effect._

sealed trait TestF[A]
case object Foo extends TestF[\/[String, Unit]]
case object Bar extends TestF[\/[String, Int]]
case object Baz extends TestF[\/[String, Int]]

type TestCoyo[A] = Coyoneda[TestF, A]
type TestFreeM[A] = Free.FreeC[TestF, A]
type Test[A] = EitherT[TestFreeM, String, A]

def lift[A](t: TestF[A]): TestFreeM[A] =
  Free.liftF[TestCoyo, A](Coyoneda.lift(t))

def foo = EitherT[TestFreeM, String, Unit] { lift(Foo) }
def bar = EitherT[TestFreeM, String, Int] { lift(Bar) }
def baz = EitherT[TestFreeM, String, Int] { lift(Baz) }

def run[A, M[_]: Monad](tio: TestFreeM[A])(interpreter: TestF ~> M): M[A] = tio.foldMap[M](new (TestCoyo ~> M) {
  def apply[A](cy: TestCoyo[A]): M[A] =
    interpreter(cy.fi).map(cy.k)
})

def testToIO: TestF ~> IO = new (TestF ~> IO) {
  def apply[A](t: TestF[A]): IO[A] = t match {
    case Foo          => IO { println(t); \/-(Unit) }
    case Bar          => IO { println(t); \/-(42) }
    case Baz          => IO { println(t); -\/("Bad call") }
  }
}

val program = for {
  _ <- foo
  a <- bar
  b <- baz
  _ <- foo
} yield (a, b)

val result = run(program)(testToIO)
result.unsafePerformIO