Functional Programming in Scala in 2023

chapter1.adoc  |  258 +++++++-----
chapter2.adoc  |  543 +++++++++++++++---------
chapter3.adoc  | 1112 ++++++++++++++++++++++++++++++++++++------------
chapter4.adoc  |  893 +++++++++++++++++++++++++++++----------
chapter5.adoc  |  767 +++++++++++++++++++++++++--------
chapter6.adoc  |  756 ++++++++++++++++++++++++---------
chapter7.adoc  | 1095 ++++++++++++++++++++++++++++++-----------------
chapter8.adoc  | 1279 ++++++++++++++++++++++++++++++++++++++++---------------
chapter9.adoc  | 1369 ++++++++++++++++++++++++++++++++++++++++++-----------------
chapter10.adoc | 1085 +++++++++++++++++++++++++++++++++++++++--------
chapter11.adoc | 1174 +++++++++++++++++++++++++++++++++++++++------------
chapter12.adoc | 1635 ++++++++++++++++++++++++++++++++++++++++++++++++++++------------------
chapter13.adoc | 1493 +++++++++++++++++++++++++++++++++++++++++++---------------------
chapter14.adoc |  620 +++++++++++++++------------
chapter15.adoc | 1921 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------------------------

Type Classes

package leopards

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

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

package leopards

trait Semigroup[A]:
  def combine(x: A, y: A): A
  extension (x: A)
    inline def |+|(y: A): A = combine(x, y)    (1)

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

1	Guilt-free operators

package leopards

given intAdditionMonoid: Monoid[Int] with
  def combine(x: Int, y: Int) = x + y
  def empty = 0

scala> import leopards.given
scala> 1 |+| 2
val res0: Int = 3

package leopards

given optionMonoid[A: Semigroup]: Monoid[Option[A]] with
  def empty = None
  def combine(x: Option[A], y: Option[A]) =
    x match
      case None => y
      case Some(xx) =>
        y match
          case None     => x
          case Some(yy) => Some(xx |+| yy)

scala> import leopards.given
scala> Option(1) |+| Option(2)
val res0: Option[Int] = Some(3)

package leopards

given optionMonoid[A](using $sa: Semigroup[A]): Monoid[Option[A]] with
  def empty = None
  def combine(x: Option[A], y: Option[A]) =
    x match
      case None => y
      case Some(xx) =>
        y match
          case None     => x
          case Some(yy) => Some($sa.combine(xx, yy))

scala> import leopards.given
scala> Option(1) |+| Option(2)
val res0: Option[Int] = Some(3)

package leopards

given mapMonoid[A, B: Semigroup]: Monoid[Map[A, B]] with
  val empty = Map.empty
  def combine(x: Map[A, B], y: Map[A, B]) =
    y.foldLeft(x):
      case (acc, (k, v)) =>
        acc.updatedWith(k)(_ |+| Some(v))

package leopards

given mapMonoid[A, B](using $sb: Semigroup[B]): Monoid[Map[A, B]] with
  val empty = Map.empty
  def combine(x: Map[A, B], y: Map[A, B]) =
    y.foldLeft(x):
      case (acc, (k, v)) =>
        acc.updatedWith(k)(ov2 =>
          optionMonoid(using $sb).combine(ov2, Some(v)))

package leopards

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

extension [A](as: IterableOnce[A])
  def combineAll(using m: Monoid[A]): A =
    as.iterator.foldLeft(m.empty)(m.combine)

  def foldMap[B](f: A => B)(using m: Monoid[B]): B =
    as.iterator.foldLeft(m.empty)((acc, a) => acc |+| f(a))

def bag[A](as: IterableOnce[A]): Map[A, Int] =
  as.foldMap(a => Map(a -> 1))

scala> val charOccurs = bag("scala".toList)
val charOccurs: Map[Char, Int] = Map(s -> 1, c -> 1, a -> 2, l -> 1)

def bag[A](as: IterableOnce[A]): Map[A, Int] =
  as.foldMap(a => Map(a -> 1))(using mapMonoid[A, Int](using intAdditionMonoid))

scala> val charOccurs = bag("scala".toList)
val charOccurs: Map[Char, Int] = Map(s -> 1, c -> 1, a -> 2, l -> 1)

Type Classes in Scala 2

import simulacrum._

@typeclass trait Semigroup[A] {
  @op("|+|") def combine(x: A, y: A): A
}

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

object Semigroup {
  def apply[A](implicit instance: Semigroup[A]): Semigroup[A] = instance

  trait Ops[A] {
    def typeClassInstance: Semigroup[A]
    def self: A
    def |+|(y: A): A = typeClassInstance.combine(self, y)
  }

  trait ToSemigroupOps {
    implicit def toSemigroupOps[A](target: A)(implicit tc: Semigroup[A]): Ops[A] = new Ops[A] {
      val self = target
      val typeClassInstance = tc
    }
  }

  object nonInheritedOps extends ToSemigroupOps

  trait AllOps[A] extends Ops[A] {
    def typeClassInstance: Semigroup[A]
  }

  object ops {
    implicit def toAllSemigroupOps[A](target: A)(implicit tc: Semigroup[A]): AllOps[A] = new AllOps[A] {
      val self = target
      val typeClassInstance = tc
    }
  }
}

Functors

package leopards

trait Functor[F[_]]:
  extension [A](fa: F[A])
    def map[B](f: A => B): F[B]
    def as[B](b: B): F[B] = map(_ => b)
    def void: F[Unit] = as(())

  def lift[A, B](f: A => B): F[A] => F[B] =
    _.map(f)

package leopards

trait Applicative[F[_]] extends Functor[F]:
  def pure[A](a: A): F[A]
  extension [A](fa: F[A])
    def map2[B, C](fb: F[B])(f: (A, B) => C): F[C]

    override def map[B](f: A => B): F[B] =
      map2(pure(()))((a, _) => f(a))

package leopards

trait Monad[F[_]] extends Applicative[F]:
  extension [A](fa: F[A])
    def flatMap[B](f: A => F[B]): F[B]

    override def map[B](f: A => B): F[B] =
      flatMap(f andThen pure)

    override def map2[B, C](fb: F[B])(f: (A, B) => C): F[C] =
      fa.flatMap(a => fb.map(b => f(a, b)))

package leopards

trait Foldable[F[_]]:
  extension [A](fa: F[A])
    def foldLeft[B](b: B)(f: (B, A) => B): B
    def foldRight[B](b: B)(f: (A, B) => B): B
    def foldMap[B](f: A => B)(using b: Monoid[B]): B =
      foldRight(b.empty)((a, b) => f(a) |+| b)

package leopards

trait Traverse[F[_]] extends Functor[F], Foldable[F]:
  extension [A](fa: F[A])
    def traverse[G[_], B](f: A => G[B])(using Applicative[G]): G[F[B]]

  extension [G[_], A](fga: F[G[A]])
    def sequence(using Applicative[G]): G[F[A]] = fga.traverse(identity)

Snippet of chapter 12 of Functional Programming in Scala

FPiS ⇒ Scala 2

Feature	Scala 2	Scala 3
Type classes	Simulacrum	Built-in
Type lambdas	Kind Projector	Built-in
Arity & data polymorphism	Shapeless	Built-in
Derivation	Shapeless	Built-in
Partial unification (SI-2712)	-Ypartial-unification (2.11+)	Built-in
Enumerations & ADTs	sealed trait hierarchies, Enumeratum et al	Built-in

Feature

Scala 2

Scala 3

Type classes

Simulacrum

Built-in

Type lambdas

Kind Projector

Built-in

Arity & data polymorphism

Shapeless

Built-in

Derivation

Shapeless

Built-in

Partial unification (SI-2712)

-Ypartial-unification (2.11+)

Built-in

Enumerations & ADTs

sealed trait hierarchies, Enumeratum et al

Built-in

😱 Composition in Scalaz

val vname = validateName(name)
val vbday = validateBirthday(bday)
val vphone = validatePhone(phone)

val personInfo = (vname |@| vbday |@| vphone)(PersonInfo(_, _, _))

DSL implemented with ApplicativeBuilder{N} types
Supports composing up to 12 values

😱 Composition in Cats

val vname = validateName(name)
val vbday = validateBirthday(bday)
val vphone = validatePhone(phone)

val personInfo = (vname, vbday, vphone).mapN(PersonInfo(_, _, _))

Replaces DSL with regular tuples
Syntax enrichments generated at build time (of cats-core) with a source generator
Supports composing up to 22 values

😱 Composition in Scala 3

trait Applicative[F[_]] extends Functor[F]:
  def pure[A](a: A): F[A]
  extension [A](fa: F[A]) def map2[B, C](fb: F[B])(f: (A, B) => C): F[C]

  extension [T <: NonEmptyTuple](tuple: T)
    def mapN[B](using Tuple.IsMappedBy[F][T])(f: Tuple.InverseMap[T, F] => B): F[B] =
      t.tupled.map(f)

    def tupled(using Tuple.IsMappedBy[F][T]): F[Tuple.InverseMap[T, F]] =
      ???

😱 Composition in Scala 3

trait Applicative[F[_]] extends Functor[F]:
  def pure[A](a: A): F[A]
  extension [A](fa: F[A]) def map2[B, C](fb: F[B])(f: (A, B) => C): F[C]

  extension [T <: NonEmptyTuple](tuple: T)
    def mapN[B](using Tuple.IsMappedBy[F][T])(f: Tuple.InverseMap[T, F] => B): F[B] =
      t.tupled.map(f)

    def tupled(using Tuple.IsMappedBy[F][T]): F[Tuple.InverseMap[T, F]] =
      def loop[X <: NonEmptyTuple](x: X): F[NonEmptyTuple] = x match
        case (hd: F[a] @unchecked) *: EmptyTuple =>
          hd.map(_ *: EmptyTuple)
        case (hd: F[a] @unchecked) *: (tl: NonEmptyTuple) =>
          val tail = loop(tl)
          hd.map2(tail)(_ *: _)
      loop(t).asInstanceOf[F[Tuple.InverseMap[T, F]]]

Efficient but requires casting / type checks

😱 Composition in Scala 3

trait Applicative[F[_]] extends Functor[F]:
  def pure[A](a: A): F[A]
  extension [A](fa: F[A]) def map2[B, C](fb: F[B])(f: (A, B) => C): F[C]

  extension [T <: NonEmptyTuple](tuple: T)
    inline def mapN[B](using Tuple.IsMappedBy[F][T])(f: Tuple.InverseMap[T, F] => B): F[B] =
      t.tupled.map(f)

    inline def tupled(using m: Tuple.IsMappedBy[F][T]): F[Tuple.InverseMap[T, F]] =
      tupledGeneric(m(t))

  private case class IsMap[T <: Tuple](value: Tuple.Map[T, F])

  private inline def tupledGeneric[X <: Tuple](x: Tuple.Map[X, F]): F[X] =
    inline IsMap(x) match
      case t: IsMap[h *: EmptyTuple] => t.value.head.map(_ *: EmptyTuple)
      case t: IsMap[h *: t] =>
        val head = t.value.head
        val tail = tupledGeneric(t.value.tail)
        head.map2(tail)(_ *: _)

Type safe but runtime overhead
Courtesy of Daniel Beskin (@ncreep)

Transformers

Allow selection of a different functor
Often considered difficult to use
Introduce additional wrapping, which leads to concerns over performance

def fetchEmployee: IO[Option[Employee]] = ???
def fetchPayInfo: IO[Option[PayInfo]] = ???

def generatePayStub(employee: Employee, payInfo: PayInfo): PayStub = ???

val payStub: IO[Option[PayStub]] =
  (fetchEmployee, fetchPayInfo).mapN(generatePayStub)

[error] Found:    PayStub
[error] Required: Option[PayStub]
[error]   (fetchEmployee, fetchPayInfo).mapN(generatePayStub)
[error]                                      ^^^^^^^^^^^^^^^

package leopards

opaque type OptionT[F[_], A] = F[Option[A]]

object OptionT:
  def apply[F[_], A](o: F[Option[A]]): OptionT[F, A] = o

  extension [F[_], A](fa: OptionT[F, A])
    def value: F[Option[A]] = fa

  given [F[_]](using F: Monad[F]): Monad[[X] =>> OptionT[F, X]] with
    def pure[A](a: A) = F.pure(Some(a))
    extension [A](ota: OptionT[F, A])
      def flatMap[B](f: A => OptionT[F, B]): OptionT[F, B] =
        F.flatMap(ota)(oa => oa.fold(F.pure(None))(f))

def fetchEmployee: IO[Option[Employee]] = ???
def fetchPayInfo: IO[Option[PayInfo]] = ???

def generatePayStub(employee: Employee, payInfo: PayInfo): PayStub = ???

val payStub: IO[Option[PayStub]] =
  (OptionT(fetchEmployee), OptionT(fetchPayInfo))
    .map(generatePayStub)
    .value

package leopards

opaque type Kleisli[F[_], A, B] = A => F[B]

object Kleisli:
  def apply[F[_], A, B](f: A => F[B]): Kleisli[F, A, B] = f

  extension [F[_], A, B](k: Kleisli[F, A, B]) def apply(a: A): F[B] = k(a)

  given [F[_], A](using F: Monad[F]): Monad[[X] =>> Kleisli[F, A, X]] with
    def pure[B](b: B) = Kleisli(_ => F.pure(b))
    extension [B](k: Kleisli[F, A, B])
      def flatMap[C](f: B => Kleisli[F, A, C]) =
        a => k(a).flatMap(b => f(b)(a))

Derivation

//> using scala 3.3.1
//> using dep io.circe::circe-core:0.14.6

import io.circe.Codec, io.circe.syntax.*

case class Person(
  firstName: String, lastName: String, age: Int) derives Codec.AsObject

val p = Person("Michael", "Pilquist", 43)
println(p.asJson)
// {
//   "firstName" : "Michael",
//   "lastName" : "Pilquist",
//   "age" : 43
// }

s/leopards/cats/

import cats.syntax.all.*

vs.

import cats.given

Tuckman Model of Functional Scala

Forming

Melting pot of styles; heavy influence from Haskell

Storming

Typelevel founded; scalac forked; Cats founded; integration painful

Norming

Cats, Cats Effect, & FS2 emerge as key infrastructure, enabling proliferation of interoperable libraries

Performing

Industrial grade, performant, integrated infrastructure; cross-platform; focus on application development

Headwinds

Improvements to Java & Kotlin
- Loom
- Coroutines
- Records
Direct Style

"Just as the past eight years have brought about a sea change in the nature of the Scala ecosystem and the context in which we evaluate and employ functional techniques, so too will the coming eight years bring about evolution and innovation. Perhaps when it comes time to update this volume once again, names such as Cats Effect will seem as dated and ancestral as Scalaz seems to us today."

— Daniel Spiewak, Foreword to FPiS