Free Applicative
API Documentation: FreeApplicative
FreeApplicative
s are similar to Free
(monads) in that they provide a nice way to represent
computations as data and are useful for building embedded DSLs (EDSLs). However, they differ
from Free
in that the kinds of operations they support are limited, much like the distinction
between Applicative
and Monad
.
Dependency
If you'd like to use cats' free applicative, you'll need to add a library dependency
for the cats-free
module.
Example
Consider building an EDSL for validating strings - to keep things simple we'll just have a way to check a string is at least a certain size and to ensure the string contains numbers.
sealed abstract class ValidationOp[A]
case class Size(size: Int) extends ValidationOp[Boolean]
case object HasNumber extends ValidationOp[Boolean]
Much like the Free
monad tutorial, we use smart constructors to lift our algebra into the FreeApplicative
.
import cats.free.FreeApplicative
import cats.free.FreeApplicative.lift
type Validation[A] = FreeApplicative[ValidationOp, A]
def size(size: Int): Validation[Boolean] = lift(Size(size))
val hasNumber: Validation[Boolean] = lift(HasNumber)
Because a FreeApplicative
only supports the operations of Applicative
, we do not get the nicety
of a for-comprehension. We can however still use Applicative
syntax provided by Cats.
import cats.syntax.all._
val prog: Validation[Boolean] = (size(5), hasNumber).mapN { case (l, r) => l && r}
As it stands, our program is just an instance of a data structure - nothing has happened at this point. To make our program useful we need to interpret it.
import cats.Id
import cats.arrow.FunctionK
import cats.syntax.all._
// a function that takes a string as input
type FromString[A] = String => A
val compiler = new FunctionK[ValidationOp, FromString] {
def apply[A](fa: ValidationOp[A]): FromString[A] = str =>
fa match {
case Size(size) => str.size >= size
case HasNumber => str.exists(c => "0123456789".contains(c))
}
}
val validator = prog.foldMap[FromString](compiler)
// validator: FromString[Boolean] = cats.instances.Function1Instances$$anon$7$$Lambda$14539/0x00007faeee6e2598@4515e7a5
validator("1234")
// res0: Boolean = false
validator("12345")
// res1: Boolean = true
Differences from Free
So far everything we've been doing has been not much different from Free
- we've built
an algebra and interpreted it. However, there are some things FreeApplicative
can do that
Free
cannot.
Recall a key distinction between the type classes Applicative
and Monad
- Applicative
captures the idea of independent computations, whereas Monad
captures that of dependent
computations. Put differently Applicative
s cannot branch based on the value of an existing/prior
computation. Therefore when using Applicative
s, we must hand in all our data in one go.
In the context of FreeApplicative
s, we can leverage this static knowledge in our interpreter.
Parallelism
Because we have everything we need up front and know there can be no branching, we can easily write a validator that validates in parallel.
import cats.data.Kleisli
import cats.syntax.all._
import scala.concurrent.Future
import scala.concurrent.ExecutionContext.Implicits.global
// recall Kleisli[Future, String, A] is the same as String => Future[A]
type ParValidator[A] = Kleisli[Future, String, A]
val parCompiler = new FunctionK[ValidationOp, ParValidator] {
def apply[A](fa: ValidationOp[A]): ParValidator[A] = Kleisli { str =>
fa match {
case Size(size) => Future { str.size >= size }
case HasNumber => Future { str.exists(c => "0123456789".contains(c)) }
}
}
}
val parValidator = prog.foldMap[ParValidator](parCompiler)
Logging
We can also write an interpreter that simply creates a list of strings indicating the filters that
have been used - this could be useful for logging purposes. Note that we need not actually evaluate
the rules against a string for this, we simply need to map each rule to some identifier. Therefore
we can completely ignore the return type of the operation and return just a List[String]
- the
Const
data type is useful for this.
import cats.data.Const
import cats.syntax.all._
type Log[A] = Const[List[String], A]
val logCompiler = new FunctionK[ValidationOp, Log] {
def apply[A](fa: ValidationOp[A]): Log[A] = fa match {
case Size(size) => Const(List(s"size >= $size"))
case HasNumber => Const(List("has number"))
}
}
def logValidation[A](validation: Validation[A]): List[String] =
validation.foldMap[Log](logCompiler).getConst
logValidation(prog)
// res2: List[String] = List("size >= 5", "has number")
logValidation(size(5) *> hasNumber *> size(10))
// res3: List[String] = List("size >= 5", "has number", "size >= 10")
logValidation((hasNumber, size(3)).mapN(_ || _))
// res4: List[String] = List("has number", "size >= 3")
Why not both?
It is perhaps more plausible and useful to have both the actual validation function and the logging strings. While we could easily compile our program twice, once for each interpreter as we have above, we could also do it in one go - this would avoid multiple traversals of the same structure.
Another useful property Applicative
s have over Monad
s is that given two Applicative
s F[_]
and
G[_]
, their product type FG[A] = (F[A], G[A])
is also an Applicative
. This is not true in the general
case for monads.
Therefore, we can write an interpreter that uses the product of the ParValidator
and Log
Applicative
s
to interpret our program in one go. We can create this interpreter easily by using FunctionK#and
.
import cats.data.Tuple2K
type ValidateAndLog[A] = Tuple2K[ParValidator, Log, A]
val prodCompiler: FunctionK[ValidationOp, ValidateAndLog] = parCompiler and logCompiler
val prodValidation = prog.foldMap[ValidateAndLog](prodCompiler)
The way FreeApplicative#foldMap works
Despite being an imperative loop, there is a functional intuition behind FreeApplicative#foldMap
.
The new FreeApplicative
's foldMap
is a sort of mutually-recursive function that operates on an argument stack and a
function stack, where the argument stack has type List[FreeApplicative[F, _]]
and the functions have type List[Fn[G, _, _]]
.
Fn[G[_, _]]
contains a function to be Ap
'd that has already been translated to the target Applicative
,
as well as the number of functions that were Ap
'd immediately subsequently to it.
Main re-association loop
Pull an argument out of the stack, eagerly remove right-associated Ap
nodes, by looping on the right and
adding the Ap
nodes' arguments on the left to the argument stack; at the end, pushes a single function to the
function stack of the applied functions, the rest of which will be pushed in this loop in later iterations.
Once all of the Ap
nodes on the right are removed, the loop resets to deal with the ones on the left.
Here's an example FreeApplicative
value to demonstrate the loop's function, at the end of every iteration.
Every node in the tree is annotated with an identifying number and the concrete type of the node
(A -> Ap
, L -> Lift
, P -> Pure
), and an apostrophe to denote where argF
(the current argument) currently
points; as well the argument and function branches off Ap
nodes are explicitly denoted.
==> begin.
'1A
/ \
arg/ \fun
/ \
/ \
2A 3A
arg/ \fun arg/ \fun
/ \ / \
4L 5P 6L 7L
args: Nil
functions: Nil
==> loop.
1A
/ \
arg/ \fun
/ \
/ \
2A '3A
arg/ \fun arg/ \fun
/ \ / \
4L 5P 6L 7L
args: 2A :: Nil
functions: Nil
==> loop.
1A
/ \
arg/ \fun
/ \
/ \
2A 3A
arg/ \fun arg/ \fun
/ \ / \
4L 5P 6L '7L
args: 6L :: 2A :: Nil
functions: Fn(gab = foldArg(7L), argc = 2) :: Nil
==> finished.
At the end of the loop the entire right branch of Ap
s under argF
has been peeled off into a single curried function,
all of the arguments to that function are on the argument stack and that function itself is on the function stack,
annotated with the amount of arguments it takes.
Function application loop
Once argF
isn't an Ap
node, a loop runs which pulls functions from the stack until it reaches a curried function,
in which case it applies the function to argF
transformed into a G[Any]
value, and pushes the resulting function
back to the function stack, before returning to the main loop.
I'll continue the example from before here:
==> loop.
1A
/ \
arg/ \fun
/ \
/ \
2A 3A
arg/ \fun arg/ \fun
/ \ / \
4L 5P '6L 7L
args: 2A :: Nil
functions: Fn(gab = foldArg(7L) ap foldArg(6L), argc = 1) :: Nil
==> finished.
At the end of this loop every function on the top of the function stack with length == 1
(not curried)
has been applied to a single argument from the argument stack, and the first curried function (length != 1
)
on the stack has been applied to a single argument from the argument stack.
The reason we can't keep applying the curried function to arguments is that the node on top of the argument
stack must be an Ap
node if the function is curried, so we can't translate it directly to G[_]
.
Once the last function has been applied to the last argument, the fold has finished and the result is returned.
References
Deeper explanations can be found in this paper Free Applicative Functors by Paolo Capriotti