Cats Free Monad based algebras composition

Question

Suppose I've got the following algebra for working with file system:

sealed trait Fs[A]
case class Ls(path: String) extends Fs[Seq[String]]
case class Cp(from: String, to: String) extends Fs[Unit]

def ls(path: String) = Free.liftF(Ls(path))
def cp(from: String, to: String) = Free.liftF(Cp(from, to))

And the following interpreter for the algebra:

def fsInterpreter = new (Fs ~> IO) {
  def apply[A](fa: Fs[A]) = fa match {
    case Ls(path) => IO(Seq(path))
    case Cp(from, to) => IO(())
  }
}

Now suppose I want to build another algebra that uses the first one. E.g.:

sealed trait PathOps[A]
case class SourcePath(template: String) extends PathOps[String]

def sourcePath(template: String) = Free.liftF(SourcePath(template))

The next thing I want to write an interpreter for PathOps ~> IO which would do something like this:

for {
  paths <- ls(template)
} yield paths.head

In other words my interpreter for PathOps should call into Fs algebra.

How do I do that?

There's a full example of this exact problem in the cats docs: typelevel.org/cats/datatypes/freemonad.html (section: Composing Free monads ADTs.) — erdeszt
Unfortunately I don't think that section answers my question. It does explain how to compose 2 mutually independent ADTs when building a program. It doesn't however cover a case when the interpreter for one ADT relies on the other ADT — Alexandr Antonov
@AlexandrAntonov Could it be that you want to compose two FunctionK-~>-nat trafos PathOps ~> Free[Fs, ?] and Fs ~> IO? That is: does your desired natural trafo PathOps ~> IO somehow factor through the Free[Fs, ?]-monad? — Andrey Tyukin

Andrey Tyukin Andrey Tyukin · Accepted Answer · 2018-03-12T17:24:06

I assume that you want to write two interpreters PathOps ~> Free[Fs, ?] and Fs ~> IO, and then to compose them into a single interpreter PathOps ~> IO.

A compilable example follows. Here are all the imports that I used for this example:

import cats.~>
import cats.free.Free
import cats.free.Free.liftF

Here is a mock-implementation of IO and your algebras:

// just for this example
type IO[X] = X 
object IO {
  def apply[A](a: A): IO[A] = a
}

sealed trait Fs[A]
case class Ls(path: String) extends Fs[Seq[String]]
case class Cp(from: String, to: String) extends Fs[Unit]
type FreeFs[A] = Free[Fs, A]

def ls(path: String) = Free.liftF(Ls(path))
def cp(from: String, to: String) = Free.liftF(Cp(from, to))

This is the interpreter Fs ~> IO copied from your code:

def fsToIoInterpreter = new (Fs ~> IO) {
  def apply[A](fa: Fs[A]) = fa match {
    case Ls(path) => IO(Seq(path))
    case Cp(from, to) => IO(())
  }
}

sealed trait PathOps[A]
case class SourcePath(template: String) extends PathOps[String]

def sourcePath(template: String) = Free.liftF(SourcePath(template))

This is your for-comprehension converted into a PathOps ~> Free[Fs, ?]-interpreter:

val pathToFsInterpreter = new (PathOps ~> FreeFs) {
  def apply[A](p: PathOps[A]): FreeFs[A] = p match {
    case SourcePath(template) => {
      for {
        paths <- ls(template)
      } yield paths.head
    }
  }
}

Now you can lift the Fs ~> IO into an Free[Fs, ?] ~> IO using Free.foldMap, and compose it with the PathOps ~> Free[Fs, ?]-interpreter using andThen:

val pathToIo: PathOps ~> IO = 
  pathToFsInterpreter andThen 
  Free.foldMap(fsToIoInterpreter)

This gives you an interpreter from PathOps ~> IO that consists of two separate layers that can be tested separately.

Cats Free Monad based algebras composition

1 Answers