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:

1. The ability to represent recursive data definitions
2. The ability to represent HKT

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 A
• `Option[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, ?]]```

If we require `SemigroupE` and`MonoidE `implementations to follow usual `Monoid`and `Semigroup` laws,

we can be sure that

• `FreePointed[A]` is isomorphic to `Option[A]`
• `FreeSemigroup[A]` is isomorphic to `NonEmptyList[A]`
• `FreeMonoid[A]` is isomorphic to `List[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

1. `NonEmptyList` that is a subtype of `List`
2. `Option` that is a subtype of `List`
3. `single` that can create each of `Option`, `List,` and `NonEmptyList` without any type class magic
4. `empty` that can create both `List`s and `Option`s
5. `combine` that able to - concatenate two `NonEmptyList`s resulting in ```NonEmptyList ```- concatenate couple of `Option`s, `Option` and `NonEmptyList` or a couple of `List`s resulting in simple `List`

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

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 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]]
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))
}
}

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]):

fa.continue(
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 Free`IO `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 cost-free relation system between recursive types, simple or higher-kinded.

We can redefine some well-known structures as free definitions, gaining two-dimensional 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.