Implementation of the Free Arrow in Scala and other helpful tools for working with Arrows
Based on the paper Generalizing Monads to Arrows
Use Free Arrow to build a computation graph that can be interpreted to different execution contexts and reused to create more complex flows from smaller ones. Typically the Free Arrow (FreeA) is used to compose
values of some embedded DSL into a flow-like computation graph.
The primary motivation for using FreeA is to decouple the construction of a program
from its interpretation, enabling the following features:
- Create reusable and modular components to build complex programs from simpler ones
- Change the program's interpretation without altering its structure
- Statically introspect the graph to describe the flow
- Optimize/rewrite a program using results from its analysis
An example use case may be creating a data processing flow which can be used both as a stand alone function for single data points or as a stream processor. With Free Arrow, you would write the flow logic once, and have two interpreters; one for a pure function and a second for the stream processor.
First define a minmal set of operations (algebra)
sealed trait ConsoleOp[A, B] // Represents some console operation that takes an `A` and outputs `B`
case object GetLine extends ConsoleOp[Unit, String]
case object PutLine extends ConsoleOp[String, Unit]
case class Prompt(message: String) extends ConsoleOp[Unit, Unit]
case class Dictionary(dict: Map[String, String]) extends ConsoleOp[String, Option[String]]
Then define smart constructors to lift your algebra into the FreeArrow
import FreeArrow.liftK // for lifting `ConsoleOp` into `FreeA`
val getLine = liftK(GetLine)
val putLine = liftK(PutLine)
def prompt(message: String) = liftK(Prompt(message))
def dictionary(entry: (String, String)*) = liftK(Dictionary(entry.toMap))
Construct a program from your free operations
val translator =
prompt("Hello") >>>
prompt("Enter an English word to translate") >>>
getLine >>| ( // dead end, return output of `getLine` after the following
putLine.lmap("Translating " + (_: String)) >>>
prompt("...").rmap(_ => Thread.sleep(1000)).loopN(3)
) >>>
dictionary(
"apple" -> "manzana",
"blue" -> "azul",
"hello" -> "hola",
"goodbye" -> "adios")
.rmap(_.getOrElse("I don't know that one")) >>>
putLine
Write an interpreter to do something useful with your program
val functionInterpreter: ConsoleOp ~~> Function1 = new (ConsoleOp ~~> Function1) {
override def apply[A, B](f: ConsoleOp[A, B]): A => B = f match {
case Prompt(message) => _ => println(message)
case GetLine => _ => StdIn.readLine()
case PutLine => println
case Dictionary(dict) => dict.get
}
}
Interpret and run your program
val program = translator.foldMap(functionInterpreter)
program(())
// Hello
// Enter an English word to translate
// Translating hello
// ...
// ...
// ...
// holaHere's an example of introspecting the FreeArrow program to count the number of getLines used
import cats.implicits._
val numGets = translator.analyze(new (ConsoleOp ~>| Int) {
def apply[A, B](f: ConsoleOp[A, B]): Int = f match {
case GetLine => 1
case _ => 0
}
})
It is also possible to generate documentation from your free program. Here is the output of an interpreter that draws a computation graph.
FreeA is implemented as a sealed trait that supports operations from several levels of the Arrow typeclass hierarchy.
The typeclass required to run/interpret a FreeA is inferred by the operations used to build it. Only the most general and least powerful Arrow subtype will be required.
val unit: FreeA[Arrow, Nothing, Unit, Unit] = FreeA.id[Unit]
val ar: FreeA[Arrow, Nothing, Unit, Unit] = unit >>> unit
val ac: FreeA[ArrowChoice, Nothing, Either[Unit, Unit], Unit] = ar ||| ar
val az: FreeA[ArrowZero, Nothing, Unit, Unit] = ar >>> zeroArrow[Unit, Unit]
val ap: FreeA[ArrowPlus, Nothing, Unit, Unit] = az <+> ar <+> ar
// val run = ap.foldMap(BiFunctionK.id[Function1]) // wont compile,
// `Function1` does not have an ArrowPlus instance
val run = ap.foldMap(BiFunctionK.id[Function1].kleisli[List]) // compiles
// Any Kleisli[M, A, B] that has a Monad[M] and MonoidK[M] has an ArrowPlus[Kleisli[M, ?, ?]] instance
run(()) // List((), ())
Different DSLs and their interpreters can be composed together in FreeA using
FreeA.inl/FreeA.inr and the BiFunctionK.or combinators respectively.
- e.g. A
FreeA[R, ConsoleOp, A, B]and aFreeA[R, MathOp, A, B]can be combined to aEitherFreeA[R, ConsoleOp, MathOp, A, B]
As Free constructions go, here's how FreeA sits on the spectrum of power and expressiveness:
(Co)Yoneda < Free Applicative < Free Arrow < Free Monad
Free Arrow has both the static introspection of the Free Applicative and the sequencing capability of the Free Monad
FreeArrow supports both sequencing like FreeMonad and static analysis of the free structure like FreeApplicative. This allows you to write expressive programs that can be introspected and optimized for further sequential composition
Based on the talks Beyond Free Monads and Blazing Fast, Pure Effects without Monads by John A De Goes
The ZIO arrow module has been adapted from the work in https://github.com/zio-crew/zio-arrow. Only main difference that the code in this repo has is that Impure function compisition is made stack safe.
Add this to your build.sbt:
libraryDependencies += "com.adrielc" %% "free-arrow" % "<version>"Cross-builds are available for Scala 2.12.10 and 2.13.1.
Any contribution is more than welcome. Also feel free to report bugs, request features using github issues.
People are expected to follow the Scala Code Of Conduct when discussing free-arrow on the Github page, Gitter channel, or other venues.
MIT License
Written in 2020 by Adriel Casellas.