pre2.scala

import scalaz._
import Scalaz._
type Step0[F[_], S, A] = S => (S, F[A])
type Precepte[F[_], S, A] = Free[({ type L[A] = Step0[F, S, A] })#L, A]
type UnmanagedState = List[String]
type Pre[A] = Precepte[Id, UnmanagedState, A]

object Pre {
  type St[A] = Step0[Id, UnmanagedState, A]

  def pure[A](tag: String)(a: A): Pre[A] = {
    val p: Pre[A] = Free.pure[({ type L[A] = Step0[Id, UnmanagedState, A] })#L, A](a)
    substep(tag)(p)
  }

  def substep[A](tag: String)(p: Pre[A]): Pre[A] = {
    Free[St, A](s => (s :+ tag, p))
  }
}

val p1: Pre[Int] = Pre.pure("p1")(1)
val p2: Pre[Int] = Pre.pure("p2")(2)
val p3: Pre[Int] = Pre.substep("p3")(p1.flatMap(r1 => p2.map(r2 => r1 + r2)))

type Out0[A] = (UnmanagedState, Id[A])
type Out[A] = UnmanagedState => Out0[A]

implicit def m = new Monad[Out] {
  def point[A](a: => A): Out[A] = s => (s, a)
  def bind[A, B](fa: Out[A])(f: A => Out[B]): Out[B] = { s0 =>
    val (s, a) = fa(s0)
    f(a)(s)
  }
}

val nostate: UnmanagedState = Nil

def paf = new (Out ~> Out0) {
  def apply[A](fa: Out[A]) = fa(nostate)
}

p3.foldMap(paf) // (List("p3", "p1", "p2"), 3)

pre3.scala

import scalaz._, Scalaz._
type Step0[F[_], S, A] = S => F[(S, A)]
type Precepte[F[_], S, A] = Free[({ type L[A] = Step0[F, S, A] })#L, A]
type UnmanagedState = List[String]

trait PreBuilder[F[_]]{
  type Pre[A] = Precepte[F, UnmanagedState, A]
  type St[A] = Step0[F, UnmanagedState, A]

  def apply[A](tag: String)(a: A)(implicit ap: Applicative[F]): Pre[A] = {
    val p = Free[St, A] { s => (s, pure(a)).point[F] }
    substep(tag)(p)
  }

  def substep[A](tag: String)(p: Pre[A]): Pre[A] =  {
    val go = new (St ~> St) {
      def apply[A](st: St[A]) = s => st(s :+ tag)
    }
    p.mapFirstSuspension(go)
  }

  def pure[A](a: A): Pre[A] =
    Free.pure[St, A](a)
}

object Precepte  {
  def apply[F[_]] = new PreBuilder[F]{}
}

def run[F[_]] =
  new (F ~> F) {
    def apply[A](fa: F[A]) = fa
  }

implicit def mo[F[_]: Monad, S] =
  new Monad[({ type λ[α] = Step0[F, S, α] })#λ] {
    def point[A](a: => A) = s => (s, a).point[F]
    def bind[A, B](oa: Step0[F, S, A])(f: A => Step0[F, S, B]) =
      s0 => oa(s0).flatMap { case (s1, a) => f(a)(s1) }
  }

type Pre[A] = Precepte[Id, UnmanagedState, A]

val p1: Pre[Int] = Precepte[Id]("p1")(1)
val p2: Pre[Int] = Precepte[Id]("p2")(2)
val p3: Pre[Int] = Precepte[Id].substep("p3")(p1.flatMap(r1 => p2.map(r2 => r1 + r2)))

val nostate: UnmanagedState = Nil
type S0[α] = Step0[Id, UnmanagedState, α]
val f = p3.foldMap(run[S0]) 
f(nostate)// (List("p3", "p1", "p2"), 3)