build.sbt

libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.1.0"

scalaVersion := "2.11.4"

FreeMonadList.scala

import scalaz._

object FreeMonadList extends App{

  type PairOpt[α] = Option[(α, α)]

  type List[A] = Free[PairOpt, A]

  implicit val pairOptFunctor: Functor[PairOpt] =
    new Functor[PairOpt]{
      def map[A, B](fa: PairOpt[A])(f: A => B) = fa match{
        case Some((_1, _2)) => Some((f(_1), f(_2)))
        case None => None
      }
    }

  def nil[A]: List[A] = Free.liftF[PairOpt, A](None)

  def cons[A](head: A, tail: List[A]): List[A] =
    Free.freeMonad[PairOpt].join(
      Free.liftF[PairOpt, List[A]](
        Option(Free.point[PairOpt, A](head) -> tail)
      )
    )

  def toScalaList[A](list: List[A]): scala.List[A] = {
    import std.list._
    list.foldMap(new (PairOpt ~> scala.List){
      def apply[A](a: PairOpt[A]) = a match {
        case Some((x, y)) => x :: y :: Nil
        case None => Nil
      }
    })
  }

  val list = cons(1, cons(2, cons(3, nil[Int])))

  println(toScalaList(list))
}