Scala FP- Advanced Concepts 2

Folks , i hope you had good time reading my last blog on type classes . If not , I would strongly recommend you to go through it once Scala Type Classes . The goal of this blog are two-fold : to introduce monads , functors , and other functional programming patterns and also guide you through how they are implemented in Cats !

To be honest , these constructs fall under design patterns in scala , similar to we have different design patterns in oops world . The major difference between them are :

1. they are formally, and thus precisely, defined
2. they are extremely general

So , lets start . Before diving into Cats Library constructs in scala , lets go into chapters of mathematics for sometime as it has its origin from there . In category theory following are the main constructs you will see again and again .

Lets peek into them one by one . I will take both mathematical and programmatic approach to demonstrate above concepts and patterns .

Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.The binary operation of a semigroup is most often denoted multiplicatively: x·y, or simply xy, denotes the result of applying the semigroup operation to the ordered pair (x, y). Associativity is formally expressed as that (x·y)·z = x·(y·z) for all x, y and z in the semigroup .

In Scala , If a type A can form a Semigroup it has an associative binary operation.

trait Semigroup[A] {
  def combine(x: A, y: A): A
}

Associativity means the following equality must hold for any choice of x, y, and z

combine(x, combine(y, z)) = combine(combine(x, y), z)

Examples are quite straight forward and also there is some special syntax as highlighted below :

import cats.Semigroup

implicit val intAdditionSemigroup: Semigroup[Int] = new Semigroup[Int] {
  def combine(a: Int, b: Int): Int = a + b
}
val x = 11
val y = 12
val z = 31
Semigroup[Int].combine(x, y)
// res0: Int = 23

Semigroup[Int].combine(x, Semigroup[Int].combine(y, z))
// res1: Int = 54

Semigroup[Int].combine(Semigroup[Int].combine(x, y), z)
// res2: Int = 54
import cats.implicits._
1 |+| 2  // Special Syntax
// res3: Int = 3

Monoid

In mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are semigroups with identity. Suppose that S is a set and • is some binary operation S × S → S, then S with • is a monoid if it satisfies the following two axioms:

Associativity
For all a, b and c in S, the equation (a • b) • c = a • (b • c) holds.

Identity element
There exists an element e in S such that for every element a in S, the equations e • a = a • e = a hold.

In Scala , Monoid extends the power of Semigroup by providing an additional empty value

trait Semigroup[A] {
  def combine(x: A, y: A): A
}

trait Monoid[A] extends Semigroup[A] {
  def empty: A
}

This empty value should be an identity for the combine operation, which means the following equalities hold for any choice of x

combine(x, empty) = combine(empty, x) = x

Many types that form a Semigroup also form a Monoid, such as Ints (with 0) and Strings (with "").

import cats.Monoid

implicit val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
  def empty: Int = 0
  def combine(x: Int, y: Int): Int = x + y
}

val x = 1
Monoid[Int].combine(x, Monoid[Int].empty)
// res0: Int = 1

Monoid[Int].combine(Monoid[Int].empty, x)
// res1: Int = 1

Functor

In mathematics, specifically category theory, a functor is a map between categories. Functors were first considered in algebraic topology, where algebraic objects are associated to topological spaces, and maps between these algebraic objects are associated to continuous maps between spaces.

In Scala , Functor is a type class that abstracts over type constructors that can be map‘ed over. Examples of such type constructors are List, Option, and Future.

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

// Example implementation for Option
implicit val functorForOption: Functor[Option] = new Functor[Option] {
  def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa match {
    case None    => None
    case Some(a) => Some(f(a))
  }
}

A Functor instance must obey two laws:

Composition : Mapping with f and then again with g is the same as mapping once with the composition of f and g

fa.map(f).map(g) = fa.map(f.andThen(g))

Identity : Mapping with the identity function is a no-op

fa.map(x => x) = fa

Examples for Functors :

import cats.Functor
import cats.implicits._
val listOption = List(Some(1), None, Some(2))
// listOption: List[Option[Int]] = List(Some(1), None, Some(2))

// Through Functor#compose
Functor[List].compose[Option].map(listOption)(_ + 1)
// res1: List[Option[Int]] = List(Some(2), None, Some(3))

Folks , I will cover rest of the topics in subsequent blogs . I would strongly recommend you to practice above examples on your own IDE and play with them a bit . Till the next blog , happy learning !