Sunday, January 17, 2021

Tagless Final in Scala for Beginners

This post is an effort to explain what is tagless-final in Scala and if one has bumped into strange-looking F[_] notations and wondered what it is, where, and how it is used, then this post will also try to answer those questions. There's nothing new to learn for a seasoned functional programmer, but this would give a head start for anyone beginning on the journey. Let's walk through it step-by-step.

What's a type constructor?

Simply put, something that constructs types can be considered as a type constructor. For example, List can be considered as a type constructor because it has the ability to construct types based on what type argument is passed to its constructor. 
As per the type theory, List would be both a type (denoted by *) and type-constructor (denoted by * -> *)

val list: List.type = List
val intList: List[Int] = list[Int]()

In the above code snippet, Int is passed to the variable list (which is of type List) as an argument, i.e Int is the type argument to List type list.

What are higher-kinded types?

A higher-kinded type can be considered as something that abstracts over the type constructor. As a continuation of the above example of List, abstraction over the type constructor can be done with the help of using the F[_] notation, for example:

trait Test[F[_]]
val test = new Test[List] {}
val test = new Test[Option] {}
val test = new Test[Vector] {}

In the above code snippet, trait Test provides the ability to abstracts over the type constructor with the help of F[_] notation, and hence it is possible to pass List type constructor to it. And for that matter, it is also possible to pass other type constructors as well, for example, Option, Vector, etc. In this code snippet, Test now becomes a higher-kinded type.

What's an Effect in functional programming?

Do not confuse Effect with a side-effect! A side-effect can be one of the Effect but it is not the only Effect. An Effect can be considered as something that can happen within a Wrapper. For example, consider the Wrapper to be an Either. Now, anything that happens inside an Either can be considered as an Effect, as shown below:

def work[A, B](value: A)(fn: A => B): Either[Throwable, B] =
  try Right(fn(value))
  catch {
    case ex: Exception => Left(ex)

work("1")(_.toInt) // Right(1)
work("T")(_.toInt) // Left(NumberFormatException)

The method work is considered as an Effectful method as instead of returning just the value B, it is returning Either[Throwable, B] so the caller of the method will know what to expect from the method's return type. A method can be considered as Effectful if it returns F[B] instead of B and F in the above example is Either.

What's a type class?

A type class can be considered as a class that defines a common behavior that can be associated with some types (data types). A common behavior could be anything, for example, an Adder type class that defines behaviors for the addition of data types like Int, Double, Float, etc.

trait Adder[A] {
  def add(value1: A, value2: A): A

Additionally, a type class should also be lawful in the sense that it should follow certain algebraic laws, in the case of the Adder type class above, it should follow the laws of associativity which is tantamount to it being a Semigroup. 

What's ad-hoc polymorphism with respect to a type class?

The behavior of adding two numeric values specific to a data type can be achieved by method overloading in a normal OOPs setting, for example:

case class Age(v: Int)

def add(value1: Int, value2: Int): Int = value1 + value2
def add(value1: Double, value2: Double): Double = value1 + value2
def add(value1: Age, value2: Age): Age = Age(value1.v + value2.v)
But this would result in some code duplication and a more generic way to write this would be using the method definition as seen from the Adder type class example above:
def add(value1: A, value2: A): A

But how would add know what is the way to add two values, the values could be Int or they could very well be Age data type. A way to do it is by using the type classes, their instances tied to specific data types, and injecting datatype specific instances to the method using implicits in Scala, giving ad-hoc polymorphism capabilities.

case class Age(v: Int)

trait Adder[A] {
  def add(value1: A, value2: A): A

object Adder {
  def apply[A: Adder]: Adder[A]              = implicitly[Adder[A]]
  def add[A: Adder](value1: A, value2: A): A = Adder[A].add(value1, value2)

object AdderInstances {
  implicit val intAdder: Adder[Int] = (value1, value2) => value1 + value2
  implicit val ageAdder: Adder[Age] = (value1, value2) => Age(Adder[Int].add(value1.v, value2.v))

import AdderInstances._
Adder.add(25, 25) // 50
Adder.add(Age(25), Age(25)) // Age(50)

What's tagless-final?

Let's look at a dumbed-down representation of a Stock Market with capabilities to buy and sell financial instruments.

import cats.Monad
import cats.effect.IO
import cats.implicits._
import scala.language.higherKinds

sealed trait OrderType
case object Buy  extends OrderType
case object Sell extends OrderType

sealed trait FinancialInstrument {
  val id: String
  val quantity: Int
  val price: Float
  val orderType: OrderType

case class FutureDerivativeInstrument(id: String, quantity: Int, price: Float, orderType: OrderType) extends FinancialInstrument
case class OptionDerivativeInstrument(id: String, quantity: Int, price: Float, orderType: OrderType) extends FinancialInstrument
case class EquityCashInstrument(id: String, quantity: Int, price: Float, orderType: OrderType)       extends FinancialInstrument

trait StockMarket[F[_]] {
  def buyInstrument(instrument: FinancialInstrument): F[FinancialInstrument]
  def sellInstrument(instrument: FinancialInstrument): F[FinancialInstrument]

object StockMarketInstances {
  implicit val instrument: StockMarket[IO] = new StockMarket[IO] {
    override def buyInstrument(instrument: FinancialInstrument): IO[FinancialInstrument]  = IO(instrument)
    override def sellInstrument(instrument: FinancialInstrument): IO[FinancialInstrument] = IO(instrument)

object StockMarket {
  def apply[F[_]: StockMarket]: StockMarket[F] = implicitly[StockMarket[F]]

  def executeBuyOrder[F[_]: StockMarket](instrument: FinancialInstrument): F[FinancialInstrument]  = StockMarket[F].buyInstrument(instrument)
  def executeSellOrder[F[_]: StockMarket](instrument: FinancialInstrument): F[FinancialInstrument] = StockMarket[F].sellInstrument(instrument)

def placeOrder[F[_]: StockMarket: Monad](orders: Vector[FinancialInstrument]): F[Vector[FinancialInstrument]] = {
  orders.pure[F].flatMap { instruments =>
    instruments.traverse { instrument =>
      instrument.orderType match {
        case Buy  => StockMarket[F].buyInstrument(instrument)
        case Sell => StockMarket[F].sellInstrument(instrument)

import StockMarketInstances._
placeOrder[IO](Vector(OptionDerivativeInstrument("SA-121", 50, 100, Buy), FutureDerivativeInstrument("DS-991", 50, 100, Sell))).unsafeRunSync()

Here, StockMarket is a tagless-final type class that describes the capabilities of generic type F[_]. The core concept of tagless-final is declaring dependencies for which Scala's implicits are used.

Tagless-final pattern enables:

  • Capability to abstract over the higher-kinded type providing means to use any of the available Effect types in place of F, like Cats Effect IO, or Task, or Monix. That is, it enables Effect type indirection.
  • Ability to reason about the implementation of the polymorphic function (in the example above, the placeOrder function) by looking at the implicits required in order to be able to successfully use it. From placeOrder signature, it can be seen the function needs or uses an instance of StockMarket and Applicative to implement its functionality. That is, it enables Effect parametric reasoning.
  • The inclination to use the principle of least power by declaring only those type classes as implicit parameters that are needed for the placeOrder function implementation.
As an end note, it is only by following a disciplined approach as noted above the tagless-final would be useful but is not something that comes automatically just by using it.

No comments:

Post a Comment