Scala, Free Monad and TAPL

FreeIdZero.scala

import scalaz.Functor
import scalaz.Free

sealed trait Term[+A]
object Term {
  case object Zero extends Term[Nothing]
  case class Id[A](term: A) extends Term[A]

  implicit val termFunctor: Functor[Term] = new Functor[Term] {
    def map[A, B](fa: Term[A])(f: A => B): Term[B] = fa match {
      case Zero => Zero
      case Id(t) => Id(f(t))
    }
  }

  def zero[A]: Free[Term, A] = Free.Suspend(Zero)
  def id[A](term: Free[Term, A]): Free[Term, A] = Free.Suspend(Id(term))
}

type Value = Term[Nothing]

import Free._
import Term._

def eval(t: Term[Free[Term, Value]]): Free[Term, Value] = t match {
  case Zero => Return(Zero)
  case Id(t) => t
}

val t = id(id(zero))

val smallStep = t.bounce(eval)
// => smallStep: scalaz.Free[Term,Value] = Suspend(Id(Suspend(Zero)))

val bigStep = t.go(eval)
// => bigStep: Value = Zero