Open in app

Sign in

Write

Sign in

Final Free Structures with Subtyping (Scala)

Oleg Nizhnik
6 min readJun 3, 2019

--

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

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 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, ?]]

What’s so special about it?

If we require SemigroupE andMonoidE implementations to follow usual Monoidand 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 Lists and Options
  5. combine that able to
    - concatenate two NonEmptyLists resulting in NonEmptyList
    - concatenate couple of Options, Option and NonEmptyList or a couple of Lists 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 Applicativeallowing 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 InjectKs 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 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. NonEmptyLists and Options are subtypes of Lists, and FreeApplicatives and FreeSelectives are subtypes of FreeMonads

Code

All the code samples presented in this package

manatki/manatki

scala cats things. Contribute to manatki/manatki development by creating an account on GitHub.

github.com

Thanks

Special thanks to https://twitter.com/katzenstrophe for the help in preparing this post.

Functional Programming
Final Tagless
Subtyping
Free Structures
Adt

--

--

Oleg Nizhnik

Written by Oleg Nizhnik

119 Followers

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams