1. Overview

Whether we prefer to use object-oriented programming or functional programming, every paradigm has its own patterns to manage dependencies among modules when managing big programs. In recent years, functional programmers prefer the Tagless Final pattern.

Let’s have a look at how to implement it in Scala.

2. Dependencies

We’ll shallow-refer to some functional types in the Cats and Cats Effect libraries during the article. To use these libraries, we need to import their dependencies in SBT:

libraryDependencies += "org.typelevel" %% "cats-effect_2.12" % "2.1.4"

3. The Challenges

As experienced functional developers, we know that learning the basic notions of functional programming – such as referential transparency, lambda calculus, functors, and monads – is only the first step.

The first time we need to approach a non-trivial program, we must understand how to manage constraints among modules to avoid a functional big ball of mud.

For example, let’s build a program that deals with shopping carts on an e-commerce site. First thing first, we need a representation of our domain model:

case class Product(id: String, description: String)
case class ShoppingCart(id: String, products: List[Product])

However, it’s not enough. We need some functions to deal with the domain model:

def create(id: String): Unit
def find(id: String): Option[ShoppingCart]
def add(sc: ShoppingCart, product: Product): ShoppingCart

The first problem with these functions is that they perform some side effects for sure. The create function will probably persist information on a database, as will the add function. The find function will eventually retrieve a shopping cart from a database, and this operation can eventually fail.

Fortunately, many Scala libraries allow developers to encapsulate the operation description that produces side effects inside some declarative contexts. Such contexts are called effects. We can use the type of a function to describe the value it will produce and the side effects through the effect pattern. Hence, the description of the side effect is separated from its execution. Libraries such as Cats Effects, Monix, or even ZIO, provide us some effect types.

For example, we can use the generic IO[T] effect from Cats. Hence, our function becomes:

def create(id: String): IO[Unit]
def find(id: String): IO[Option[ShoppingCart]]
def add(sc: ShoppingCart, product: Product): IO[ShoppingCart]

The best property about using an effect library is to continue to reason about our programs as pure functions. However, we now have to deal with the effect during the testing phase, which isn’t always obvious.

The second problem with our functions on shopping carts is that we don’t know where to put the code that implements them. Should we use a single concrete class? Or should we use an abstract trait and separate implementations?

Let’s try to give a solution to the above problems, entering the Tagless Final pattern.

4. The Tagless Final Pattern

In Scala, many patterns have been applied through the years to answer the above-mentioned problems. The Free pattern is one of these. However, many developers have been choosing another pattern in the last few years: The Tagless Final pattern.

Even though some developers criticize the pattern, or at least its blinded application in every case, the tagless final pattern offers an elegant solution to the above problem.

First thing first, what is the tagless final encoding pattern? The pattern, born in the Haskell community, lets us embed a DSL into a host language. Even though the semantic has diverged from the original in Scala, the pattern’s main aim is to use interfaces as much as possible. In the pattern jargon, we call such interfaces algebras.

4.1. Algebras

Algebras represent the DSL specific to the domain that we want to model. They represent both syntax and semantics of the DSL through the types and the signatures of their functions.

Algebras should be purely abstract. In our example, we introduced the IO effect to model side effects performed by our functions. Hence, we cannot refer directly to the IO type in the algebra because it is a concrete implementation of an effect.

To overcome this problem, we can use higher-kinded types and make the definitions of our functions abstract again:

trait ShoppingCarts[F[_]] {
  def create(id: String): F[Unit]
  def find(id: String): F[Option[ShoppingCart]]
  def add(sc: ShoppingCart, product: Product): F[ShoppingCart]

Here, the F[_] type constructor represents any generic type having a single type parameter. For example, it can represent the generic type Either[String, T] or any of the effects we presented earlier — for example, IO[T]. As a best practice, we don’t specify any constraint on the F[_] type constructor during the algebra definition. In this way, we can implement the algebra without any prior assumption.

So, the DSL of our ShoppingCarts algebra defines three operations on the ShoppingCart domain model:

  • Creating a new shopping cart, given an identifier
  • Searching for a shopping cart associated with a given identifier
  • Adding a product to a given shopping cart

In the wild, algebras are called using many different conventions. For example, some developers use suffixes such as ShoppingCartService, ShoppingCartAlgebra, ShoppingCartAlg. Instead, we preferred the domain model’s plural form.

4.2. Interpreters

Now, it’s time to implement some concrete behavior. If algebras represent pure abstract objects, we need some implementations of them, called interpreters. An interpreter defines how an algebra should behave on its terms: the inputs and outputs of its functions.

Hence, interpreters deal with the concrete implementations of functions. Moreover, we can decide to bind a concrete effect to the F[_] type constructor or to stay abstract. Finally, they encapsulate any state or dependency needed to achieve the desired function.

Normally, an algebra has at least two interpreters: a production interpreter and a test interpreter. Let’s implement a test interpreter for the ShoppingCarts algebra. For the sake of simplicity, we’ll model the persistence layer using a simple Map[String, ShoppingCart], and we use the State monad to handle it in a functional flavor:

type ShoppingCartRepository = Map[String, ShoppingCart]
type ScRepoState[A] = State[ShoppingCartRepository, A]

Hence, the type ScRepoState[A] represents a generic state transition from an instance of a ShoppingCartRepository to another, eventually producing a value of type A. Generally speaking, it’s equivalent to a function with type ShoppingCartRepository -> (ShoppingCartRepository, A).

Then, the ScRepoState[A] type constructor becomes the binding of the abstract F[_] term in the algebra:

implicit object TestShoppingCartInterpreter extends ShoppingCarts[ScRepoState] {
  override def create(id: String): ScRepoState[Unit] =
    State.modify { carts =>
      val shoppingCart = ShoppingCart(id, List())
      carts + (id -> shoppingCart)
  override def find(id: String): ScRepoState[Option[ShoppingCart]] =
    State.inspect { carts =>
  override def add(sc: ShoppingCart, product: Product): ScRepoState[ShoppingCart] =
    State { carts =>
      val products = sc.products
      val updatedCart = sc.copy(products = product :: products)
      (carts + (sc.id -> updatedCart), updatedCart)

Despite the implementation details, using the duality between algebras and interpreters, we solved both the problem of abstracting the effect – making the testing phase of our business logic easier – and how to arrange the code that implements the business logic.

However, our algebras clients still need a way to retrieve a concrete instance of an interpreter. Though the original pattern doesn’t mention them, the clients play an important role in the game. Especially, they drive how we want to make our interpreters available.

5. Programs

We call the clients of algebras programs. While the term program is not officially part of the pattern, it’s quite frequently used among developers. A program is a piece of code that uses algebras and interpreters to implement the business logic.

As it can combine the functions of many algebras, a program might need to add some constraints to the abstract algebras’ F[_] type constructor. For example, imagine we need to develop a function that creates a new shopping cart, and then it immediately adds a new product to it. Hence, we need to execute the two operations, both defined in the ShoppingCarts algebras, in sequence. There’s no way of parallelizing them.

As we know, the functional structure that allows sequencing operations over an effect is the monad. So, we need an instance of the type class Monad[F] to be available in the context of our program. Scala has a dedicated syntax for such situations, called type constraints:

def createAndAddToCart[F[_] : Monad] = ???

When applying constraints to type constructors, we must always remember the principle of least power. Since, as functional developers, we should always guess the meaning of a function only by looking at its signature, if we request constraints that are too slack, we lose this important tool of understanding.

Say that instead of Monad, we request a constraint to the IO[F] type:

def createAndToCart[F[_] : IO] = ???

What can we say about this function? The IO monad models any operation that requests a side effect, from possibly raising an exception to launching nuclear missiles.

5.1. Implicit Object Resolution

Now, we need to retrieve an instance of a concrete interpreter. There are essentially two ways to make an interpreter available to a program: implicit object resolution and smart constructors.

In the first case, the interpreter implements an implicit object, as in our example above. Then, the program declares an implicit parameter referring to the algebra:

def createAndAddToCart[F[_] : Monad](product: Product, cartId: String)
  (implicit shoppingCarts: ShoppingCarts[F]): F[Option[ShoppingCart]] =
  for {
    _ <- shoppingCarts.create(cartId)
    maybeSc <- shoppingCarts.find(cartId)
    maybeNewSc <- maybeSc.traverse(sc => shoppingCarts.add(sc, product))
  } yield maybeNewSc

Using the implicit resolution mechanism, the Scala compiler will search for an available instance of an interpreter for the ShoppingCarts algebra in the context. Even though this pattern recalls the type classes pattern, it’s very different at the core. Indeed, we use type classes to add capabilities to an abstract effect, whereas interpreters don’t.

We might be tempted to use algebras as if they were type classes. Using this approach, we can add the ShoppingCarts algebra as a further type constraint on the F[_] type constructor:

def createAndToCart[F[_] : Monad : ShoppingCarts](product: Product, cartId: String): Unit = ???

In fact, the Scala compiler translates a type constraint on F, adding an implicit parameter to the function, obtaining a signature similar to the previous one we showed. However, we don’t have a concrete parameter with an associated name to call the ShoppingCarts algebra functions. How can we overcome this problem?

A possible solution is to use the summoned value pattern, which consists of overriding the apply method in the companion object of the algebra:

object ShoppingCarts {
  def apply[F[_]](implicit sc: ShoppingCarts[F]): ShoppingCarts[F] = sc

We moved the interpreter’s implicit resolution into a dedicated function, using a generic function. In this way, we can refer directly to the algebra using the construct ShoppingCarts[F], which calls the apply method:

def createAndToCart[F[_] : Monad : ShoppingCarts](product: Product, cartId: String): F[Option[ShoppingCart]] =
  for {
    _ <- ShoppingCarts[F].create(cartId)
    maybeSc <- ShoppingCarts[F].find(cartId)
    maybeNewSc <- maybeSc.traverse(sc => ShoppingCarts[F].add(sc, product))
  } yield maybeNewSc

However, as we said, algebras and interpreters are not applying the type classes pattern, as they don’t share the same scope. So, many developers consider it a bad practice to add algebras as an effect type constraint.

As a rule of thumb, use implicit object resolution if and only if the module to resolve is a type class or something infrastructural such as logging, which doesn’t contain any business logic at all.

5.2. Smart Constructor

The other option for a program that needs an algebra instance is to pass it explicitly as an input parameter. We will use no implicit resolution this time. Hence, we’re going to apply the smart constructor pattern.

First of all, we need our interpreter to become a class, not just an object, because we want to have full control of the instantiation process. So, we make the constructor private. Being a regular class, we can eventually pass the dependencies in the constructor:

class ShoppingCartsInterpreter private(repo: ShoppingCartRepository)
  extends ShoppingCarts[ScRepoState] {
  // Functions implementation

Then, we want to instantiate an interpreter using a factory method. In this way, we can implement any verification on inputs, if needed. Hence, we put the factory method in the interpreter companion object, giving it a sound name such as make:

object ShoppingCartsInterpreter {
  def make(): ShoppingCartsInterpreter = {
    new ShoppingCartsInterpreter(repository)
  private val repository: ShoppingCartRepository = Map()

In this case, the factory method does not take any input parameter, and we resolve the only dependency of the interpreter inside the companion object. A different approach requires giving such dependency directly as a parameter of the make function.

What about the program? To avoid implicit resolution of the interpreter, we must provide the dependency directly as a parameter. Instead of using an explicit parameter to the createAndAddToCart function, we can use a class to model a module for the program:

case class ProgramWithDep[F[_] : Monad](carts: ShoppingCarts[F]) {
  def createAndToCart(product: Product, cartId: String): F[Option[ShoppingCart]] = {
    for {
      _ <- carts.create(cartId)
      maybeSc <- carts.find(cartId)
      maybeNewSc <- maybeSc.traverse(sc => carts.add(sc, product))
    } yield maybeNewSc

So, the client code of the program will provide the interpreter using the smart constructor to the program:

val program: ProgramWithDep[ScRepoState] = ProgramWithDep {
program.createAndToCart(Product("id", "a product"), "cart1")

6. Conclusion

In this long article, we introduced the tagless final pattern in Scala. The pattern uses the concepts of algebras, interpreters, and programs to organize code responsibilities among modules. In this way, the code remains clean, and it’s easier to evolve, reuse, and test.

As always, the code is available over on GitHub.

1 Comment
Inline Feedbacks
View all comments
17 days ago

Great article, there are several opinions here that I can definitely agree on (such as when to use implicits vs passing dependencies as regular parameters, ie. use constructors). Will definitely share this with colleagues and friends!