FP cheat sheet

As a software engineer with strong object oriented background I need a functional programming design patterns cheat sheet. Otherwise, I feel lost.

Credits:

Semigroup

Associative binary operation. The binary operation takes two elements of the set as input and produces a single output element of the set.

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

Definition:

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

Concatenate of two strings:

1
2
3
import cats.kernel.Semigroup

Semigroup[String].combine("A", "B") // "AB"

Add values of each key in the maps:

1
2
3
4
5
6
import cats.kernel.Semigroup

val map1 = Map("a" -> 1, "b" -> 2, "c" -> 3)
val map2 = Map("b" -> 3, "c" -> 4, "d" -> 5)

Semigroup[Map[String, Int]].combine(map1, map2) // Map(a -> 1, b -> 5, c -> 7, d -> 5)

Add values of each option if both are defined, or by returning the defined option, or else None:

1
2
3
4
5
6
7
8
import cats.kernel.Semigroup

val combine: (Option[Int], Option[Int]) => Option[Int] = Semigroup[Option[Int]].combine(_, _)

combine(Some(1), Some(2)) // Some(3)
combine(Some(1), None) // Some(1)
combine(None, Some(1)) // Some(1)
combine(None, None) // None

Add values of each try if both are successful, or by returning the first failed try, or else the second failed try:

1
2
3
4
5
6
7
8
9
10
11
import scala.util.{Try, Success, Failure}
import cats.kernel.Semigroup

val combine: (Try[Int], Try[Int]) => Try[Int] = Semigroup[Try[Int]].combine(_, _)

val f = Failure(new Exception())

combine(Success(1), Success(2)) // Success(3)
combine(Success(1), f) // Failure(java.lang.Exception)
combine(f, Success(1)) // Failure(java.lang.Exception)
combine(f, f) // Failure(java.lang.Exception)

Monoid

A Monoid is a Semigroup that has an identity element. An identity element is a value that when combined with any other value of the same type using Semigroup, produces that other value as the result.

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

Definition:

1
2
3
4
trait Monoid[A] {
  def combine(x: A, y: A): A
  def empty: A
}

Sum of integers but use the Monoid’s identity element to represent the missing value:

1
2
3
4
5
6
import cats.kernel.Monoid
import cats.syntax.semigroup._

val numbers = List(Some(1), None, Some(3), Some(4))

numbers.fold(Monoid[Option[Int]].empty)(_ |+| _) // Some(8)

Functor

Generalizable map:

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

fa.map(x => x) = fa

map

Definition:

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

For example:

1
2
def increment[F[_]](container: F[Int])(using functor: Functor[F]): F[Int] =
  functor.map(container)(_ + 1)

Or using extension method:

1
2
3
import cats.syntax.functor._
def increment[F[_]](container: F[Int])(using functor: Functor[F]): F[Int] =
  functor.map(container)(_ + 1)

Contravariant Functor

1
def contramap[A, B](fa: F[A])(f: B => A): F[B]

contramap

Invariant Functor

Definition:

1
def imap[B](dec: A => B, enc: B => A): Codec[B]

imap

For example:

1
2
3
4
5
def longToDate: Long => Date = new Date(_)
def dateToLong: Date => Long = _.getTime

val semigroupDate: Semigroup[Date] =
  Semigroup[Long].imap(longToDate)(dateToLong)

Monad

Mechanism for sequencing computations:

pure(a).flatMap(func) == func(a)

m.flatMap(pure) == m

m.flatMap(f).flatMap(g) == m.flatMap(x => f(x).flatMap(g))

Definition:

1
2
3
4
trait Monad[F[_]] {
  def pure[A](value: A): F[A]
  def flatMap[A, B](value: F[A])(func: A => F[B]): F[B]
}

option flatmap

Identity Monad

Effect of having no effect:

1
type Id[A] = A

Kleisli

Composition of functions that return a monadic value:

1
2
3
4
final case class Kleisli[F[_], A, B](run: A => F[B]) {
  def compose[Z](k: Kleisli[F, Z, A])(implicit F: FlatMap[F]): Kleisli[F, Z, B] =
    Kleisli[F, Z, B](z => k.run(z).flatMap(run))
}

Semigroupal

Combine contexts:

product(a, product(b, c)) == product(product(a, b), c)

Definition:

1
2
3
trait Semigroupal[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

Applicative Functor

Definition:

1
2
3
4
5
6
7
trait Applicative[F[_]] extends Semigroupal[F] with Functor[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]

  def pure[A](a: A): F[A]

  def map[A, B](fa: F[A])(f: A => B): F[B] = ap(pure(f))(fa)
}

For example:

1
val applicativeList = Applicative[List].pure(42)

Or using extension method:

1
2
import cats.syntax.applicative._
val applicativeList = 42.pure[List]

Foldable

1
2
3
4
trait Foldable[F[_]] {
  def foldLeft[A, B](fa: F[A], b: B)(f: (A, B) => B): B
  def foldRight[A, B](fa: F[A], b: B)(f: (A, B) => B): B
}

Fold List(1, 2, 3)

Traverse

1
2
3
4
5
6
7
8
trait Traverse[F[_]] {
  def traverse[G[_]: Applicative, A, B]
      (inputs: F[A])(func: A => G[B]): G[F[B]]

  def sequence[G[_]: Applicative, B]
      (inputs: F[G[B]]): G[F[B]] =
    traverse(inputs)(identity)
}

For example, if F is List and G is Option[Int]:

1
2
3
4
def parseInt(s: String): Option[Int] = ???

List("1","2","3").traverse(parseInt) == Some(List(1,2,3))
List("1","a","3").traverse(parseInt) == None