Final Free Structures with Subtyping (Scala)
Recap
In the previous post, we’ve discovered this beautiful structure
trait Capture[F[_]] {
def continue[A](k: F[A]): A
}
If some functor representing the tagless continuation of some data is provided as F[_]
, Capture[F]
would represent an initial form of such data.
Contravariance can help represent unions in terms of intersections and vice versa, using the duality.
Capture[F] & Capture[G] = Capture[F  G]
Capture[F]  Capture[G] = Capture[F & G]
Still, we haven’t touched most useful properties of tagless final encoding yet:
 The ability to represent recursive data definitions
 The ability to represent HKT
Let’s start with recursion
Free Construction
There are a lot of recursive data structures representing some free constructions.
The one everyone loves is List[A]
which is a known form of a free monoid.
Other examples are:
NonEmptyList[A]
is a free semigroup for AOption[A]
is a free pointed set for A
Let’s define corresponding definitions
trait PointedE[A, B] extends (A => B) { def empty: B }trait SemigroupE[A, B] extends Semigroup[B] with (A => B)trait MonoidE[A, B] extends Monoid[B] with SemigroupE[A, B] with PointedE[A, B]
Each of those definitions includes some Algebra[B]
paired with embedding A => B.
Having this definition of free structure
trait FreeStruct[Algebra[_], A]{
def continue[B](embed: A => B, algebra: Algebra[B]): B
}
We’re just merging two arguments into the single trait resulting in
trait FreeStruct[AlgE[_, _], A]{
def continue[B](algebraAndEmbed: AlgE[A, B]): B
}
This may be simplified as
type FreeStruct[AlgE[_, _], A] = Capture[AlgE[A, ?]]
Having this form we can define the following
type FreeSemigroup[+A] = Capture[SemigroupE[A, ?]]
type FreeMonoid[+A] = Capture[MonoidE[A, ?]]
type FreePointed[+A] = Capture[PointedE[A, ?]]
What’s so special about it?
If we require SemigroupE
andMonoidE
implementations to follow usual Monoid
and Semigroup
laws,
we can be sure that
FreePointed[A]
is isomorphic toOption[A]
FreeSemigroup[A]
is isomorphic toNonEmptyList[A]
FreeMonoid[A]
is isomorphic toList[A]
Let’s start from the Option
:
def fromOption[A](opt: Option[A]): FreePointed[A] = new Capture[PointedE[A, ?]] { def continue[B](k: PointedE[A, B]): B = opt.fold(k.empty)(k.apply) }def toOption[A](opt: FreePointed[A]): Option[A] = opt.continue(new PointedE[A, Option[A]] { def empty: Option[A] = None def apply(a: A): Option[A] = Some(a) })
Next, take the NonEmptyList
:
def fromNel[A](nel: NonEmptyList[A]): FreeSemigroup[A] = new Capture[SemigroupE[A, ?]] { def continue[B](k: SemigroupE[A, B]): B = nel.reduceMap(k.apply)(k) }def toNel[A](nel: FreeSemigroup[A]): NonEmptyList[A] = nel.continue(new SemigroupE[A, NonEmptyList[A]] { def apply(a: A): NonEmptyList[A] = NonEmptyList.one(a) def combine(x: NonEmptyList[A], y: NonEmptyList[A]): NonEmptyList[A] = x ::: y })
And finally the List
def fromList[A](l: List[A]): FreeMonoid[A] = new Capture[MonoidE[A, ?]] { def continue[B](k: MonoidE[A, B]): B = l.foldMap(k.apply)(k) }def toList[A](l: FreeMonoid[A]): List[A] = l.continue(new MonoidE[A, List[A]] { def apply(a: A): List[A] = List(a) def empty: List[A] = Nil def combine(x: List[A], y: List[A]): List[A] = x ::: y })
Now we can define some basic constructors
def single[A](a: A): Capture[A => ?] = new Capture[A => ?] { def continue[B](k: A => B): B = k(a) }def combine[A, F[x] <: SemigroupE[A, x]]( xs: Capture[F], ys: Capture[F]): Capture[F] = new Capture[F] { def continue[B](k: F[B]): B = k.combine(xs.continue(k), ys.continue(k)) }def empty[A, F[x] <: PointedE[A, x]]: Capture[F] = new Capture[F] { def continue[B](k: F[B]): B = k.empty }
The intriguing property of this representation is the ability to embed free constructions via subtyping
FreeSemigroup[A] <: FreeMonoid[A]
FreePointed[A] <: FreeMonoid[A]
Particularly we achieved
NonEmptyList
that is a subtype ofList
Option
that is a subtype ofList
single
that can create each ofOption
,List,
andNonEmptyList
without any type class magicempty
that can create bothList
s andOption
scombine
that able to  concatenate twoNonEmptyList
s resulting inNonEmptyList
 concatenate couple ofOption
s,Option
andNonEmptyList
or a couple ofList
s resulting in simpleList
So we now have a lot of data relations without special type classes, representing them.
Definitions
Before we continue, we need to make a few additional definitions
First is a selective functor
This is just an extension of Applicative
allowing for conditional effect composition.
We define such as
trait Selective[F[_]] extends Applicative[F] {
def select[A, B](fab: F[Either[A, B]], fa: => F[B]): F[B]
}
The second one is just a redefinition of FunctionK having variance marks on type parameters
trait FunK[F[_], +G[_]] {
def apply[A](fa: F[A]): G[A]
}
That gives us more subtyping when we apply functor embedding
Higher Kinded Types
Now it’s time to remind the Functor power hierarchy
Functor Pure
 
V 
Applicative <+

V
Selective

V
Monad
Each of these definitions could have a free form like Free Monad or Free Applicative
Unluckily we are forced to define each free ADT separately, copying common constructors, and translating between using folds
We can start from this upgrade of Capture
trait Capture1[K[_[_]], A] {
def continue[F[_]](k: K[F]): F[A]
}
This is pretty much like the previous one, but continuation algebra is now higher kinded. We might represent functor capabilities using it.
We define our Embedding Algebras:
trait PureE[F[_], G[_]] extends FunK[F, G] with Pure[G]trait FunctorE[F[_], G[_]] extends FunK[F, G] with Functor[G]trait ApplicativeE[F[_], G[_]] extends FunctorE[F, G] with PureE[F, G] with Applicative[G]trait SelectiveE[F[_], G[_]] extends ApplicativeE[F, G] with Selective[G]trait MonadE[F[_], G[_]] extends Monad[G] with SelectiveE[F, G] { def select[A, B](fab: G[Either[A, B]], fa: => G[B]): G[B] = flatMap(fab) { case Left(a) => fa case Right(b) => pure(b) } }
And the collection of free functorial Structures
type FreeF[+F[_], A] = Capture1[FunK[F, ?[_]], A]type FreeFunctor[+F[_], A] = Capture1[FunctorE[F, ?[_]], A]type FreePure[+F[_], A] = Capture1[PureE[F, ?[_]], A]type FreeApplicative[+F[_], A] = Capture1[ApplicativeE[F, ?[_]], A]type FreeSelective[+F[_], A] = Capture1[SelectiveE[F, ?[_]], A]type FreeMonad[+F[_], A] = Capture1[MonadE[F, ?[_]], A]
Now we’ll start defining our instances. First one is Pure
trait PureInstance[F[_], K[g[_]] <: PureE[F, g]] extends Pure[Capture1[K, ?]] { override def pure[A](x: A) = new Capture1[K, A] { def continue[G[_]](k: K[G]): G[A] = k.pure(x) } }implicit def pure[F[_]]: Pure[FreePure[F, ?]] = new PureInstance[F, PureE[F, ?[_]]] {}
Next one is Functor
trait FunctorInstance[F[_], K[g[_]] <: FunctorE[F, g]] extends Functor[Capture1[K, ?]] { override def map[A, B](fa: Capture1[K, A])(f: A => B) = new Capture1[K, B] { def continue[G[_]](k: K[G]): G[B] = k.map(fa.continue(k))(f) } }implicit def functor[F[_]]: Functor[FreeFunctor[F, ?]] = new FunctorInstance[F, FunctorE[F, ?[_]]] {}
Why do we have some strange type parameter like
K[g[_]] <: PureE[F, g]
or K[g[_]] <: FunctorE[F, g]
?
It allows us to reuse our instance implementation to implement more powerful instances, let’s continue with Applicative
trait ApplicativeInstance[F[_], K[g[_]] <: ApplicativeE[F, g]] extends Applicative[Capture1[K, ?]] with FunctorInstance[F, K] with PureInstance[F, K] { override def ap[A, B] (ff: Capture1[K, A => B]) (fa: Capture1[K, A]) = new Capture1[K, B] { def continue[G[_]](k: K[G]): G[B] = k.ap(ff.continue(k))(fa.continue(k)) } }implicit def applicative[F[_]]: Applicative[FreeApplicative[F, ?]] = new ApplicativeInstance[F, ApplicativeE[F, ?[_]]] {}
Then Selective
trait SelectiveInstance[F[_], K[g[_]] <: SelectiveE[F, g]]
extends Selective[Capture1[K, ?]]
with ApplicativeInstance[F, K] {
def select[A, B]
(fab: Capture1[K, Either[A, B]],
fa: => Capture1[K, B]) =
new Capture1[K, B] {
def continue[G[_]](k: K[G]): G[B] =
k.select(fab.continue(k), fa.continue(k))
}
}
implicit def selective[F[_]]: Selective[FreeSelective[F, ?]] =
new SelectiveInstance[F, SelectiveE[F, ?[_]]] {}
And finally her highness Monad
trait MonadInstance[F[_], K[g[_]] <: MonadE[F, g]]
extends StackSafeMonad[Capture1[K, ?]]
with SelectiveInstance[F, K] {
def flatMap[A, B]
(fa: Capture1[K, A])
(f: A => Capture1[K, B]) =
new Capture1[K, B] {
def continue[G[_]](k: K[G]): G[B] =
k.flatMap(fa.continue(k))(a => f(a).continue(k))
}
}
implicit def monad[F[_]]: Monad[FreeMonad[F, ?]] =
new MonadInstance[F, MonadE[F, ?[_]]] {}
The most useful constructor: embedding of any HKT application within any free structure
def embed[F[_], A](fa: F[A]): FreeF[F, A] =
new FreeF[F, A] {
def continue[G[_]](k: FunK[F, G]): G[A] = k(fa)
}
We define simple isomorphism with cats.free.Free
to show we didn’t lose any power
def fromFreeMonad[F[_], A](fa: cats.free.Free[F, A]):
FreeMonad[F, A] =
fa.foldMap[FreeMonad[F, ?]](functionK[F](fa => embed(fa)))
def toFreeMonad[F[_], X](fa: FreeMonad[F, X]): Free[F, X] =
fa.continue(
new MonadE[F, Free[F, ?]] with StackSafeMonad[Free[F, ?]] {
def pure[A](a: A): Free[F, A] =
Free.pure(a)
def apply[A](fa: F[A]): Free[F, A] =
Free.liftF(fa)
def flatMap[A, B](fa: Free[F, A])
(f: A => Free[F, B]): Free[F, B] =
fa.flatMap(f)
})
One can easily verify that
FreeApplicative[F] <: FreeMonad[F]
and also for each F[_] <: G[_]
FreeMonad[F] <: FreeMonad[G]
That property can be extremely useful since we might use
FreeMonad[Console  UserStore  Authorization, ?]
instead of nasty InjectK
s like
[F[_]
: Console :<: ?[_]
: UserStore :<: ?[_]
: Authorization :<: ?[_] ] Free[F]
And have Free monads with nice type inference and seamless embedding
Also, we can express more powerful types like FreeIO
monad with precise effect control and effect system, powered by subtyping, pretty much like ZIO but allowing to embed any functor and control async/concurrency capabilities, but this is a theme for the following posts.
Conclusion
Final algebraic form along with contravariance gives a chance to build powerful costfree relation system between recursive types, simple or higherkinded.
We can redefine some wellknown structures as free definitions, gaining twodimensional subtyping control:
 Covariance on base set (alphabet)
 Contravariance on algebra structure
Latter means that more restrictive (based on weaker algebras) data structures are subtypes for less restrictive. NonEmptyList
s and Option
s are subtypes of List
s, and FreeApplicative
s and FreeSelective
s are subtypes of FreeMonad
s
Code
All the code samples presented in this package
Thanks
Special thanks to https://twitter.com/katzenstrophe for the help in preparing this post.