Scala Free Monads with Coproduct and monad transformer

Question

I'm trying to start using free monads in my project and I'm struggling to make it elegant.
Let's say I have two contexts (in reality I have more) - Receipt and User - both have operations on a database and I would like to keep their interpreters separate and compose them at the last moment.
For this I need to define different operations for each and combine them into one type using Coproduct.
This is what I have after days of googling and reading:

  // Receipts
sealed trait ReceiptOp[A]
case class GetReceipt(id: String) extends ReceiptOp[Either[Error, ReceiptEntity]]

class ReceiptOps[F[_]](implicit I: Inject[ReceiptOp, F]) {
  def getReceipt(id: String): Free[F, Either[Error, ReceiptEntity]] = Free.inject[ReceiptOp, F](GetReceipt(id))
}

object ReceiptOps {
  implicit def receiptOps[F[_]](implicit I: Inject[ReceiptOp, F]): ReceiptOps[F] = new ReceiptOps[F]
}

// Users
sealed trait UserOp[A]
case class GetUser(id: String) extends UserOp[Either[Error, User]]

class UserOps[F[_]](implicit I: Inject[UserOp, F]) {
  def getUser(id: String): Free[F, Either[Error, User]] = Free.inject[UserOp, F](GetUser(id))
}

object UserOps {
  implicit def userOps[F[_]](implicit I: Inject[UserOp, F]): UserOps[F] = new UserOps[F]
}

When I want to write a program I can do this:

type ReceiptsApp[A] = Coproduct[ReceiptOp, UserOp, A]
type Program[A] = Free[ReceiptsApp, A]

def program(implicit RO: ReceiptOps[ReceiptsApp], UO: UserOps[ReceiptsApp]): Program[String] = {

  import RO._, UO._

  for {
    // would like to have 'User' type here
    user <- getUser("user_id")
    receipt <- getReceipt("test " + user.isLeft) // user type is `Either[Error, User]`
  } yield "some result"
}  

The problem here is that for example user in for comprehension is of type Either[Error, User] which is understandable looking at the getUser signature.

What I would like to have is User type or stopped computation.
I know I need to somehow use an EitherT monad transformer or FreeT, but after hours of trying I don't know how to combine the types to make it work.

Can someone help? Please let me know if more details are needed.

I've also created a minimal sbt project here, so anyone willing to help could run it: https://github.com/Leonti/free-monad-experiment/blob/master/src/main/scala/example/FreeMonads.scala

Cheers, Leonti

Answer 1

After long battle with Cats:

  // Receipts
sealed trait ReceiptOp[A]
case class GetReceipt(id: String) extends ReceiptOp[Either[Error, ReceiptEntity]]

class ReceiptOps[F[_]](implicit I: Inject[ReceiptOp, F]) {
  private[this] def liftFE[A, B](f: ReceiptOp[Either[A, B]]) = EitherT[Free[F, ?], A, B](Free.liftF(I.inj(f)))

  def getReceipt(id: String): EitherT[Free[F, ?], Error, ReceiptEntity] = liftFE(GetReceipt(id))
}

object ReceiptOps {
  implicit def receiptOps[F[_]](implicit I: Inject[ReceiptOp, F]): ReceiptOps[F] = new ReceiptOps[F]
}

// Users
sealed trait UserOp[A]
case class GetUser(id: String) extends UserOp[Either[Error, User]]

class UserOps[F[_]](implicit I: Inject[UserOp, F]) {
  private[this] def liftFE[A, B](f: UserOp[Either[A, B]]) = EitherT[Free[F, ?], A, B](Free.liftF(I.inj(f)))

  def getUser(id: String): EitherT[Free[F, ?], Error, User] = Free.inject[UserOp, F](GetUser(id))
}

object UserOps {
  implicit def userOps[F[_]](implicit I: Inject[UserOp, F]): UserOps[F] = new UserOps[F]
}

Then you write program as you want:

type ReceiptsApp[A] = Coproduct[ReceiptOp, UserOp, A]
type Program[A] = Free[ReceiptsApp, A]

def program(implicit RO: ReceiptOps[ReceiptsApp], UO: UserOps[ReceiptsApp]): Program[Either[Error, String]] = {

  import RO._, UO._

  (for {
    // would like to have 'User' type here
    user <- getUser("user_id")
    receipt <- getReceipt("test " + user.isLeft) // user type is `User` now
  } yield "some result").value // you have to get Free value from EitherT, or change return signature of program 
}  

A little explanation. Without Coproduct transformer, functions would return:

Free[F, A]

Once we add Coproduct of operations into picture, return type becomes:

Free[F[_], A]

, which works fine until we try to transform it to EitherT. If there would not be Coproduct, EitherT would look like:

EitherT[F, ERROR, A]

Where F, is Free[F, A]. But if F is Coproduct and Injection is used, intuition leads to:

EitherT[F[_], ERROR, A]

Which is wrong obviously, here we have to extract type of Coproduct. Which would lead us with kind-projector plugin to:

EitherT[Free[F, ?], ERROR, A]

Or with lambda expression:

EitherT[({type L[a] = Free[F, a]})#L, ERROR, A]

Now it is correct type to which we can lift with:

EitherT[Free[F, ?], A, B](Free.liftF(I.inj(f)))

If needed, we can simplify return type to:

type ResultEitherT[F[_], A] = EitherT[Free[F, ?], Error, A]

And use it in functions like:

def getReceipt(id: String): ResultEitherT[F[_], ReceiptEntity] = liftFE(GetReceipt(id))

Answer 2

The Freek library implements all the machinery required to solve your problem:

type ReceiptsApp = ReceiptOp :|: UserOp :|: NilDSL
val PRG = DSL.Make[PRG]

def program: Program[String] = 
  for {
    user    <- getUser("user_id").freek[PRG]
    receipt <- getReceipt("test " + user.isLeft).freek[PRG]
  } yield "some result"

As you rediscovered yourself, Free monads and the likes are not extensible without going through the complexity of coproducts. If you are looking for an elegant solution, I would suggest you have a look at Tagless Final Interpreters.