Tag Archives: scala generics

A Stateful Calculator In Scala

Cats State

The Cats State is a Scala object with the defining apply method:

def apply[S, A](f: S => (S, A)): State[S, A]

1	def apply[S, A](f: S => (S, A)): State[S, A]

that takes a state-transforming function f: S => (S, A) where S represents the state type and A the result type. It returns a State[S, A] which is a type alias of StateT[Eval, S, A] (or equivalently IndexedStateT[Eval, S, S, A]).

StateT[F, S, A] takes a S state and produces an updated state and an A result wrapped in the F context. In this case, Eval which is equipped with stack-safety features is the context.

Other methods in the State object include the following:

def empty[S, A](implicit A: Monoid[A]): State[S, A]
def pure[S, A](a: A): State[S, A]
def get[S]: State[S, S]
def set[S](s: S): State[S, Unit]
def inspect[S, T](f: (S) => T): State[S, T]
def modify[S](f: (S) => S): State[S, Unit]

def empty[S, A](implicit A: Monoid[A]): State[S, A]

def pure[S, A](a: A): State[S, A]

def get[S]: State[S, S]

def set[S](s: S): State[S, Unit]

def inspect[S, T](f: (S) => T): State[S, T]

def modify[S](f: (S) => S): State[S, Unit]

along with class methods such as run, runS and runA provided by the IndexedStateT class.

A stateful post-order calculator

The simplistic calculator processes a sequence of integer arithmetic operations in a “post-order” manner to return the computed result. In each arithmetic operation, it takes a pair of integer operands followed by an arithmetic operator. For example 1 2 + 3 * would be interpreted as (1 + 2) * 3.

Implementation is straight forward. The input string consisting of the integer operands and operators (+|-|*|/) will be parsed with operands being pushed into a stack and, upon coming across an operator, popped from the stack to carry out the corresponding arithmetics.

Implementation using Scala Cats

// A post-order integer calculator implemented using Scala Cats
// (Source: Scala with Cats by Welsh and Gurnell)

import cats.data.State

def operator(op: (Int, Int) => Int): State[List[Int], Int] = {
  State[List[Int], Int] {
    case x :: y :: ls =>
      val res = op(y, x)
      (res :: ls, res)
    case _ =>
      sys.error("Missing operands error!")
  }
}

def operand(value: String): State[List[Int], Int] = {
  value.toIntOption match {
    case Some(v) =>
      State[List[Int], Int] { ls => (v :: ls, v) }
    case None =>
      sys.error(s"Operand $value type error!")
  }
}

def evalOne(sym: String): State[List[Int], Int] = {
  if (sym == "+") operator(_ + _)
  else if (sym == "-") operator(_ - _)
  else if (sym == "*") operator(_ * _)
  else if (sym == "/") operator(_ / _)
  else operand(sym)
}

def evalAll(instructions: String): State[List[Int], Int] = {
  val list = instructions.split("\\s+").toList
  list.foldLeft(State.pure[List[Int], Int](0)){ (acc, sym) =>
    acc.flatMap(_ => evalOne(sym))
  }
}

// Test running ...

evalOne("30").run(Nil).value
// (List(30),30)

evalAll("10 20 + 15 - 5 / 4 *").run(Nil).value
// (List(12),12)

// A post-order integer calculator implemented using Scala Cats

// (Source: Scala with Cats by Welsh and Gurnell)

import cats.data.State

def operator(op: (Int, Int) => Int): State[List[Int], Int] = {

State[List[Int], Int] {

case x :: y :: ls =>

val res = op(y, x)

(res :: ls, res)

case _ =>

sys.error("Missing operands error!")

}

def operand(value: String): State[List[Int], Int] = {

value.toIntOption match {

case Some(v) =>

State[List[Int], Int] { ls => (v :: ls, v) }

case None =>

sys.error(s"Operand $value type error!")

}

def evalOne(sym: String): State[List[Int], Int] = {

if (sym == "+") operator(_ + _)

else if (sym == "-") operator(_ - _)

else if (sym == "*") operator(_ * _)

else if (sym == "/") operator(_ / _)

else operand(sym)

}

def evalAll(instructions: String): State[List[Int], Int] = {

val list = instructions.split("\\s+").toList

list.foldLeft(State.pure[List[Int], Int](0)){ (acc, sym) =>

acc.flatMap(_ => evalOne(sym))

}

// Test running ...

evalOne("30").run(Nil).value

// (List(30),30)

evalAll("10 20 + 15 - 5 / 4 *").run(Nil).value

// (List(12),12)

Using State[List[Int], Int], the operands are being kept in a stack (i.e. List[Int]) within the State structure and will be extracted to carry out the integer arithmetic operations. Method operand() takes a String-typed integer and pushes into the stack, and method operator() takes a binary function (Int, Int) => Int to process the two most recently pushed integers from the stack with the corresponding arithmetic operator.

Using the two helper methods, evalOne() transforms a given operand or operator into a State[List[Int], Int]. Finally, evalAll() takes an input String of a sequence of post-order arithmetic operations, parses the content and compute the result using evalOne iteratively in a fold aggregation.

Implementing with a plain Scala class

Now, what if one wants to stick to using Scala’s standard library? Since the approach of using Cats State structure has just proved itself to be an effective one, we could come up with a simple Scala class to mimic what Cats State[S, A] does.

For what we need, we’ll minimally need a class that takes a S => (S, A) state transformation function and an equivalence of Cats State’s flatMap for chaining of operations.

case class State[S, A](r: S => (S, A)) {
  def result(s: S): (S, A) = r(s)
  def map[B](f: A => B): State[S, B] =
    State(r andThen { case (s, a) => (s, f(a)) })
  def flatMap[B](g: A => State[S, B]): State[S, B] =
    State(r andThen { case (s, a) => g(a).r(s) })
}

case class State[S, A](r: S => (S, A)) {

def result(s: S): (S, A) = r(s)

def map[B](f: A => B): State[S, B] =

State(r andThen { case (s, a) => (s, f(a)) })

def flatMap[B](g: A => State[S, B]): State[S, B] =

State(r andThen { case (s, a) => g(a).r(s) })

}

As shown in the above snippet, method flatMap is created by composing function r with a partial function via andThen. Though not needed for this particular calculator implementation, we also come up with method map, for completeness if nothing else. Method result is simply for extracting the post-transformation (S, A) tuple.

With the Scala State class, we can implement the calculator’s parsing and arithmetic operations just like how it was done using Cats State.

// A stateful post-order calculator implemented using plain Scala class

case class State[S, A](r: S => (S, A)) {
  def result(s: S): (S, A) = r(s)
  def map[B](f: A => B): State[S, B] =
    State(r andThen { case (s, a) => (s, f(a)) })
  def flatMap[B](g: A => State[S, B]): State[S, B] =
    State(r andThen { case (s, a) => g(a).r(s) })
}

def operator(op: (Int, Int) => Int): State[List[Int], Int] = {
  State[List[Int], Int] {
    case x :: y :: ls =>
      val res = op(y, x)
      (res :: ls, res)
    case _ =>
      throw new Exception("Missing operands error!")
  }
}

def operand(value: String): State[List[Int], Int] = {
  value.toIntOption match {
    case Some(v) =>
      State[List[Int], Int] { ls => (v :: ls, v) }
    case None =>
      throw new Exception(s"Operand $value type error!")
  }
}

def evalOne(sym: String): State[List[Int], Int] = {
  if (sym == "+") operator(_ + _)
  else if (sym == "-") operator(_ - _)
  else if (sym == "*") operator(_ * _)
  else if (sym == "/") operator(_ / _)
  else operand(sym)
}

def evalAll(ops: String): State[List[Int], Int] = {
  val list = ops.split("\\s+").toList
  list.foldLeft(State[List[Int], Int](_ => (Nil, 0))){ (acc, op) =>
    acc.flatMap(_ => evalOne(op))
  }
}

// Test running ...

evalOne("30").result(Nil)
// (List(30),30)

evalAll("10 20 + 15 - 5 / 4 *").result(Nil)  // (List(12),12)
// evalAll("1 2 + 3 4 + *").result(Nil)  // ((List(21),21)

// A stateful post-order calculator implemented using plain Scala class

case class State[S, A](r: S => (S, A)) {

def result(s: S): (S, A) = r(s)

def map[B](f: A => B): State[S, B] =

State(r andThen { case (s, a) => (s, f(a)) })

def flatMap[B](g: A => State[S, B]): State[S, B] =

State(r andThen { case (s, a) => g(a).r(s) })

}

def operator(op: (Int, Int) => Int): State[List[Int], Int] = {

State[List[Int], Int] {

case x :: y :: ls =>

val res = op(y, x)

(res :: ls, res)

case _ =>

throw new Exception("Missing operands error!")

}

def operand(value: String): State[List[Int], Int] = {

value.toIntOption match {

case Some(v) =>

State[List[Int], Int] { ls => (v :: ls, v) }

case None =>

throw new Exception(s"Operand $value type error!")

}

def evalOne(sym: String): State[List[Int], Int] = {

if (sym == "+") operator(_ + _)

else if (sym == "-") operator(_ - _)

else if (sym == "*") operator(_ * _)

else if (sym == "/") operator(_ / _)

else operand(sym)

}

def evalAll(ops: String): State[List[Int], Int] = {

val list = ops.split("\\s+").toList

list.foldLeft(State[List[Int], Int](_ => (Nil, 0))){ (acc, op) =>

acc.flatMap(_ => evalOne(op))

}

// Test running ...

evalOne("30").result(Nil)

// (List(30),30)

evalAll("10 20 + 15 - 5 / 4 *").result(Nil) // (List(12),12)

// evalAll("1 2 + 3 4 + *").result(Nil) // ((List(21),21)

Scala Cats Typeclasses At A Glance

Common typeclass hierarchy

For the impatient, below is a diagram highlighting the hierarchical correlation.

Semigroup and Monoid

Let’s start with the simplest ones, Semigroup and Monoid.

Semigroup comes with the abstract method combine to be implemented with the specific “combine” computational logic such as the addition of integers, union of sets, etc.

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

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

trait Semigroup[A] {

def combine(x: A, y: A): A

}

trait Monoid[A] extends Semigroup[A] {

def combine(x: A, y: A): A

def empty: A

}

Note that Monoid simply supplements Semigroup with empty as the “zero” or “identity” element, allowing aggregating operations of arbitrarily many elements (e.g. summation of numbers from an initial 0).

Example:

implicit def setSemigroup[A]: Semigroup[Set[A]] =
  new Semigroup[Set[A]] {
    def combine(s1: Set[A], s2: Set[A]) = s1 union s2
  }

// Or, using SAM for brevity
// implicit def setSemigroup[A]: Semigroup[Set[A]] = _ union _

val setSG = implicitly[Semigroup[Set[Char]]]
setSG.combine(Set('a', 'b'), Set('c'))
// Set('a', 'b', 'c')

implicit def setMonoid[A](implicit sg: Semigroup[Set[A]]): Monoid[Set[A]] =
  new Monoid[Set[A]] {
    def combine(s1: Set[A], s2: Set[A]) = sg.combine(s1, s2)
    def empty = Set()
  }

val setM = implicitly[Monoid[Set[Char]]]
List(Set('a','b'),Set('c'),Set('d','e')).
  foldLeft(setM.empty)(setM.combine(_, _))
// HashSet('e', 'a', 'b', 'c', 'd')

implicit def setSemigroup[A]: Semigroup[Set[A]] =

new Semigroup[Set[A]] {

def combine(s1: Set[A], s2: Set[A]) = s1 union s2

}

// Or, using SAM for brevity

// implicit def setSemigroup[A]: Semigroup[Set[A]] = _ union _

val setSG = implicitly[Semigroup[Set[Char]]]

setSG.combine(Set('a', 'b'), Set('c'))

// Set('a', 'b', 'c')

implicit def setMonoid[A](implicit sg: Semigroup[Set[A]]): Monoid[Set[A]] =

new Monoid[Set[A]] {

def combine(s1: Set[A], s2: Set[A]) = sg.combine(s1, s2)

def empty = Set()

}

val setM = implicitly[Monoid[Set[Char]]]

List(Set('a','b'),Set('c'),Set('d','e')).

foldLeft(setM.empty)(setM.combine(_, _))

// HashSet('e', 'a', 'b', 'c', 'd')

SemigroupK and MonoidK

With a similar correlation, SemigroupK and MonoidK are the higher-kinded version of Semigroup and Monoid, respectively. SemigroupK combines values within a given context and MonoidK ensures the existence of an “empty” context.

trait SemigroupK[F[_]] {
  def combineK[A](x: F[A], y: F[A]): F[A]
}

trait MonoidK[F[_]] extends SemigroupK[F] {
  def combineK[A](x: F[A], y: F[A]): F[A]
  def empty[A]: F[A]
}

trait SemigroupK[F[_]] {

def combineK[A](x: F[A], y: F[A]): F[A]

}

trait MonoidK[F[_]] extends SemigroupK[F] {

def combineK[A](x: F[A], y: F[A]): F[A]

def empty[A]: F[A]

}

Example:

implicit val listSemigroupK: SemigroupK[List] =
  new SemigroupK[List] {
    def combineK[A](ls1: List[A], ls2: List[A]) = ls1 ::: ls2
  }

val listSGK = implicitly[SemigroupK[List]]
listSGK.combineK(List(1,2), List(3))
// List(1, 2, 3)

implicit def listMonoidK(implicit sgk: SemigroupK[List]): MonoidK[List] =
  new MonoidK[List] {
    def combineK[A](ls1: List[A], ls2: List[A]) = sgk.combineK(ls1, ls2)
    def empty[A] = List.empty[A]
  }

val listMK = implicitly[MonoidK[List]]
List(List(1,2),List(3),List(4,5)).foldLeft[List[Int]](listMK.empty)(listMK.combineK(_, _))
// List(1, 2, 3, 4, 5)

implicit val listSemigroupK: SemigroupK[List] =

new SemigroupK[List] {

def combineK[A](ls1: List[A], ls2: List[A]) = ls1 ::: ls2

}

val listSGK = implicitly[SemigroupK[List]]

listSGK.combineK(List(1,2), List(3))

// List(1, 2, 3)

implicit def listMonoidK(implicit sgk: SemigroupK[List]): MonoidK[List] =

new MonoidK[List] {

def combineK[A](ls1: List[A], ls2: List[A]) = sgk.combineK(ls1, ls2)

def empty[A] = List.empty[A]

}

val listMK = implicitly[MonoidK[List]]

List(List(1,2),List(3),List(4,5)).foldLeft[List[Int]](listMK.empty)(listMK.combineK(_, _))

// List(1, 2, 3, 4, 5)

Functor

Functor is a higher-kinded typeclass characterized by its method map which transforms some value within a given context F via a function.

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

trait Functor[F[_]] {

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

}

Example:

implicit val listFunctor: Functor[List] =
  new Functor[List] {
    def map[A, B](ls: List[A])(f: A => B) = ls.map(f)
  }

val listF = implicitly[Functor[List]]
listF.map(List(1,2,3))(i => s"#$i!")
// List("#1!", "#2!", "#3!")

implicit val listFunctor: Functor[List] =

new Functor[List] {

def map[A, B](ls: List[A])(f: A => B) = ls.map(f)

}

val listF = implicitly[Functor[List]]

listF.map(List(1,2,3))(i => s"#$i!")

// List("#1!", "#2!", "#3!")

Monad

Monad enables sequencing of operations in which resulting values from an operation can be utilized in the subsequent one.

But first, let’s look at typeclass FlatMap.

trait FlatMap[F[_]] extends Apply[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def map[A, B](fa: F[A])(f: A => B): F[B]
  @tailrec
  def tailRecM[A, B](init: A)(f: A => F[Either[A, B]]): F[B]
}

trait FlatMap[F[_]] extends Apply[F] {

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

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

@tailrec

def tailRecM[A, B](init: A)(f: A => F[Either[A, B]]): F[B]

}

FlatMap extends Apply whose key methods aren’t what we would like to focus on at the moment. Rather, we’re more interested in method flatMap which enables sequential chaining of operations.

In addition, method tailRecM is a required implementation for stack-safe recursions on the JVM (which doesn’t natively support tail call optimization).

Monad inherits almost all its signature methods from FlatMap.

trait Monad[F[_]] extends FlatMap[F] with Applicative[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def pure[A](a: A): F[A]
  def map[A, B](fa: F[A])(f: A => B): F[B]
  @tailrec
  def tailRecM[A, B](init: A)(f: A => F[Either[A, B]]): F[B]
}

trait Monad[F[_]] extends FlatMap[F] with Applicative[F] {

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

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

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

@tailrec

def tailRecM[A, B](init: A)(f: A => F[Either[A, B]]): F[B]

}

Monad also extends Applicative which we’ll get to (along with Apply) in a bit. For now, it suffices to note that Monad inherits pure from Applicative.

Even without realizing that Monad extends Functor (indirectly through FlatMap and Apply), one could conclude that Monads are inherently Functors by implementing map using flatMap and pure.

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

1	def map[A, B](fa: F[A])(f: A => B): F[B] = flatMap(fa)(a => pure(f(a)))

Example:

trait Monad[F[_]] {  // Skipping dependent classes
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def pure[A](a: A): F[A]
  def map[A, B](fa: F[A])(f: A => B): F[B]
  def tailRecM[A, B](init: A)(f: A => F[Either[A, B]]): F[B]
}

implicit val optionMonad: Monad[Option] =
  new Monad[Option] {
    def flatMap[A, B](opt: Option[A])(f: A => Option[B]) = opt.flatMap(f)
    def pure[A](a: A) = Option(a)
    def map[A, B](opt: Option[A])(f: A => B): Option[B] = flatMap(opt)(a => pure(f(a)))
    @scala.annotation.tailrec
    def tailRecM[A, B](a: A)(f: A => Option[Either[A, B]]): Option[B] = f(a) match {
      case None => None
      case Some(leftOrRight) => leftOrRight match {
        case Left(a1) => tailRecM(a1)(f)
        case Right(b1) => Option(b1)
      }
    }
  }

val optMonad = implicitly[Monad[Option]]
optMonad.flatMap(Option(3))(i => if (i > 0) Some(s"#$i!") else None)
// Some("#3!")

trait Monad[F[_]] { // Skipping dependent classes

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

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

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

def tailRecM[A, B](init: A)(f: A => F[Either[A, B]]): F[B]

}

implicit val optionMonad: Monad[Option] =

new Monad[Option] {

def flatMap[A, B](opt: Option[A])(f: A => Option[B]) = opt.flatMap(f)

def pure[A](a: A) = Option(a)

def map[A, B](opt: Option[A])(f: A => B): Option[B] = flatMap(opt)(a => pure(f(a)))

@scala.annotation.tailrec

def tailRecM[A, B](a: A)(f: A => Option[Either[A, B]]): Option[B] = f(a) match {

case None => None

case Some(leftOrRight) => leftOrRight match {

case Left(a1) => tailRecM(a1)(f)

case Right(b1) => Option(b1)

}

val optMonad = implicitly[Monad[Option]]

optMonad.flatMap(Option(3))(i => if (i > 0) Some(s"#$i!") else None)

// Some("#3!")

Semigroupal and Apply

A higher-kinded typeclass, Semigroupal conceptually deviates from SemiGroup’s values combining operation to joining independent contexts in a tupled form “product”.

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

trait Semigroupal[F[_]] {

def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]

}

Despite the simplicity of method product (which is the only class method), Semigroupal lays out the skeletal foundation for the problem space of concurrency of independent operations, as opposed to Monad’s sequential chaining.

Next, Apply brings together the goodies of Semigroupal and Functor. Its main method ap has a rather peculiar signature that doesn’t look intuitively meaningful.

trait Apply[F[_]] extends Semigroupal[F] with Functor[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
  def map[A, B](fa: F[A])(f: A => B): F[B]
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

trait Apply[F[_]] extends Semigroupal[F] with Functor[F] {

def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]

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

def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]

}

Conceptually, it can be viewed as a specialized map in which the transformation function is “wrapped” in the context.

By restructuring the type parameters in ap[A, B] and map[A, B], method product can be implemented in terms of ap and map.

// 1: Substitute `B` with `B => (A, B)`
def map[A, B](fa: F[A])(f: A => B => (A, B)): F[B => (A, B)]

// 2: Substitute `A` with `B` and `B` with `(A, B)`
def ap[A, B](ff: F[B => (A, B)])(fb: F[B]): F[(A, B)]

// Applying 1 and 2:
def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
  ap(map(fa)(a => (b: B) => (a, b)))(fb)

// 1: Substitute `B` with `B => (A, B)`

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

// 2: Substitute `A` with `B` and `B` with `(A, B)`

def ap[A, B](ff: F[B => (A, B)])(fb: F[B]): F[(A, B)]

// Applying 1 and 2:

def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =

ap(map(fa)(a => (b: B) => (a, b)))(fb)

Applicative

trait Applicative[F[_]] extends Apply[F] {
  def pure[A](a: A): F[A]
}

trait Applicative[F[_]] extends Apply[F] {

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

}

Like how Monoid supplements SemiGroup with the empty element to form a more “self-contained” typeclass, Applicative extends Apply and adds method pure which wraps a value in a context. The seemingly insignificant inclusion makes Applicative a typeclass capable of addressing problems within a particular problem space.

Similarly, Monad takes pure from Applicative along with the core methods from FlatMap to become another “self-contained” typeclass to master a different computational problem space.

Contrary to Monad’s chaining of dependent operations, Applicative embodies concurrent operations, allowing independent computations to be done in parallel.

We’ll defer examples for Applicative to a later section.

Foldable

Foldable offers fold methods that go over (from left to right or vice versa) some contextual value (oftentimes a collection) and aggregate via a binary function starting from an initial value. It also provides method foldMap that maps to a Monoid using an unary function.

trait Foldable[F[_]] {
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
  def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]
  def foldMap[A, B: Monoid](fa: F[A])(f: A => B): B
}

trait Foldable[F[_]] {

def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B

def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]

def foldMap[A, B: Monoid](fa: F[A])(f: A => B): B

}

Note that the well known foldRight method in some Scala collections may not be stack-safe (especially in older versions). Cats uses a data type Eval in its foldRight method to ensure stack-safety.

Traverse

Traverse extends Functor and Foldable and provides method traverse. The method traverses and transforms some contextual value using a function that wraps the transformed value within the destination context, which as a requirement, is bound to an Applicative.

trait Traverse[F[_]] extends Functor[F] with Foldable[F] {
  def traverse[G[_]: Applicative, A, B](fa: F[A])(ff: A => G[B]): G[F[B]]
}

trait Traverse[F[_]] extends Functor[F] with Foldable[F] {

def traverse[G[_]: Applicative, A, B](fa: F[A])(ff: A => G[B]): G[F[B]]

}

If you’ve used Scala Futures, method traverse (and the sequence method) might look familiar.

def sequence[G[_]: Applicative, A](fg: F[G[A]]): G[F[A]] =
  traverse(fg)(identity)

1 2	def sequence[G[_]: Applicative, A](fg: F[G[A]]): G[F[A]] = traverse(fg)(identity)

Method sequence has the effect of turning a nested context “inside out” and is just a special case of traverse by substituting A with G[B] (i.e. making ff an identity function).

Example: Applicative and Traverse

To avoid going into a full-on implementation of Traverse in its general form that would, in turn, require laborious implementations of all the dependent typeclasses, we’ll trivialize our example to cover only the case for Futures (i.e. type G = Future).

First, we come up with a specialized Traverse as follows:

import scala.concurrent.{ExecutionContext, Future}

trait FutureTraverse[F[_]] {  // Skipping dependent classes
  def traverse[A, B](fa: F[A])(ff: A => Future[B]): Future[F[B]]
}

import scala.concurrent.{ExecutionContext, Future}

trait FutureTraverse[F[_]] { // Skipping dependent classes

def traverse[A, B](fa: F[A])(ff: A => Future[B]): Future[F[B]]

}

For similar reasons, let’s also “repurpose” Applicative to include only the methods we need. In particular, we include method map2 which will prove handy for implementing the traverse method for FutureTraverse.

trait Applicative[F[_]] {  // Skipping dependent classes
  def map[A, B](fa: F[A])(f: A => B): F[B]
  def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z]
  def pure[A](a: A): F[A]
}

implicit val futureApplicative: Applicative[Future] =
  new Applicative[Future] {
    implicit val ec = ExecutionContext.Implicits.global
    def map[A, B](fa: Future[A])(f: A => B): Future[B] = fa.map(f)
    def map2[A, B, Z](fa: Future[A], fb: Future[B])(f: (A, B) => Z): Future[Z] =
      (fa zip fb).map(f.tupled)
    def pure[A](a: A): Future[A] = Future.successful(a)
  }

trait Applicative[F[_]] { // Skipping dependent classes

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

def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z]

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

}

implicit val futureApplicative: Applicative[Future] =

new Applicative[Future] {

implicit val ec = ExecutionContext.Implicits.global

def map[A, B](fa: Future[A])(f: A => B): Future[B] = fa.map(f)

def map2[A, B, Z](fa: Future[A], fb: Future[B])(f: (A, B) => Z): Future[Z] =

(fa zip fb).map(f.tupled)

def pure[A](a: A): Future[A] = Future.successful(a)

}

We implement map2 by tuple-ing the Futures and binary function via zip and tupled, respectively. With the implicit Applicative[Future] in place, we’re ready to implement FutureTraverse[List].

implicit val listFutureTraverse: FutureTraverse[List] =
  new FutureTraverse[List] {
    implicit val ec = ExecutionContext.Implicits.global
    implicit val appF = implicitly[Applicative[Future]]
    def traverse[A, B](ls: List[A])(ff: A => Future[B]): Future[List[B]] = {
      ls.foldRight[Future[List[B]]](Future.successful(List.empty[B])){ (a, acc) =>
        appF.map2(ff(a), acc)(_ :: _)
      }
    }
  }

import scala.concurrent.ExecutionContext.Implicits.global

val lsFutTraverse = implicitly[FutureTraverse[List]]
lsFutTraverse.traverse(List(1,2,3)){ i =>
  if (i > 0) Future.successful(s"#$i!") else Future.failed(new Exception())
}
// Future(Success(List("#1!", "#2!", "#3!")))

implicit val listFutureTraverse: FutureTraverse[List] =

new FutureTraverse[List] {

implicit val ec = ExecutionContext.Implicits.global

implicit val appF = implicitly[Applicative[Future]]

def traverse[A, B](ls: List[A])(ff: A => Future[B]): Future[List[B]] = {

ls.foldRight[Future[List[B]]](Future.successful(List.empty[B])){ (a, acc) =>

appF.map2(ff(a), acc)(_ :: _)

}

import scala.concurrent.ExecutionContext.Implicits.global

val lsFutTraverse = implicitly[FutureTraverse[List]]

lsFutTraverse.traverse(List(1,2,3)){ i =>

if (i > 0) Future.successful(s"#$i!") else Future.failed(new Exception())

}

// Future(Success(List("#1!", "#2!", "#3!")))

As a side note, we could implement traverse without using Applicative. Below is an implementation leveraging Future’s flatMap method along with a helper function (as demonstrated in a previous blog post about Scala collection traversal).

implicit val listFutureTraverse: FutureTraverse[List] =
  new FutureTraverse[List] {
    implicit val ec = ExecutionContext.Implicits.global
    def pushToList[A](a: A)(as: List[A]): List[A] = a :: as
    def traverse[A, B](ls: List[A])(ff: A => Future[B]): Future[List[B]] = {
      ls.foldRight[Future[List[B]]](Future.successful(List.empty[B])){ (a, acc) =>
        ff(a).map(pushToList).flatMap(acc.map)
      }
    }
  }

implicit val listFutureTraverse: FutureTraverse[List] =

new FutureTraverse[List] {

implicit val ec = ExecutionContext.Implicits.global

def pushToList[A](a: A)(as: List[A]): List[A] = a :: as

def traverse[A, B](ls: List[A])(ff: A => Future[B]): Future[List[B]] = {

ls.foldRight[Future[List[B]]](Future.successful(List.empty[B])){ (a, acc) =>

ff(a).map(pushToList).flatMap(acc.map)

}

Orthogonal Typeclass In Scala

Putting all method implementations in one place

It’s worth noting that having the implicit values for method implementations defined in the companion objects for the individual classes is just one convenient way. Alternatively, these implicit values could all be defined in one place:

trait Car {
  def vin: String
  def model: String
  def price: Int
}

case class Sedan(vin: String, model: String, price: Int)

case class Sports(vin: String, model: String, price: Int)

trait Settable[T] {
  def setPrice(t: T, amount: Int): T
}

object CarOps {
  implicit val carSedan = new Settable[Sedan] {
    def setPrice(t: Sedan, amount: Int) = t.copy(price = amount)
  }

  implicit val carSports = new Settable[Sports] {
    def setPrice(t: Sports, amount: Int) = t.copy(price = amount)
  }
}

import CarOps._

implicit class CarOps[T](t: T)(implicit ev: Settable[T]) {
  def setNewPrice(amount: Int) = ev.setPrice(t, amount)
}

trait Car {

def vin: String

def model: String

def price: Int

}

case class Sedan(vin: String, model: String, price: Int)

case class Sports(vin: String, model: String, price: Int)

trait Settable[T] {

def setPrice(t: T, amount: Int): T

}

object CarOps {

implicit val carSedan = new Settable[Sedan] {

def setPrice(t: Sedan, amount: Int) = t.copy(price = amount)

}

implicit val carSports = new Settable[Sports] {

def setPrice(t: Sports, amount: Int) = t.copy(price = amount)

}

import CarOps._

implicit class CarOps[T](t: T)(implicit ev: Settable[T]) {

def setNewPrice(amount: Int) = ev.setPrice(t, amount)

}

A benefit of putting all method implementations in one place is that new methods can be added without touching the base classes – especially useful in situations where those case classes cannot be altered.

For instance, if color is also an attribute of trait Car and its child case classes, adding a new color setting method will be a trivial exercise by simply adding a setColor() method signature in trait Settable and its specific method implementations as well as setNewColor() within class CarOps.

Orthogonal type collection

Let’s see what a collection of cars looks like:

val sedan1 = Sedan("1ABC*234", "Honda Accord", 20500)
val sedan2 = Sedan("2DEF*345", "BMW 330i", 38000)
val sports1 = Sports("5MNO*678", "Ford Mustang", 34000)

val cars = List(sedan1, sedan2, sports1)
// cars: List[Product with java.io.Serializable] = List(
//   Sedan("1ABC*234", "Honda Accord", 20500.0),
//   Sedan("2DEF*345", "BMW 330i", 38000.0),
//   Sports("5MNO*678", "Ford Mustang", 34000.0)
// )

val sedan1 = Sedan("1ABC*234", "Honda Accord", 20500)

val sedan2 = Sedan("2DEF*345", "BMW 330i", 38000)

val sports1 = Sports("5MNO*678", "Ford Mustang", 34000)

val cars = List(sedan1, sedan2, sports1)

// cars: List[Product with java.io.Serializable] = List(

// Sedan("1ABC*234", "Honda Accord", 20500.0),

// Sedan("2DEF*345", "BMW 330i", 38000.0),

// Sports("5MNO*678", "Ford Mustang", 34000.0)

// )

To refine the inferred List[Product with java.io.Serializable] collection type, we could provide some type hints as shown below:

// Existential type hints
import scala.language.existentials

val cars = List[(T, Settable[T]) forSome { type T }](
    (sedan1, implicitly[Settable[Sedan]]),
    (sedan2, implicitly[Settable[Sedan]]),
    (sports1, implicitly[Settable[Sports]])
  )

// Existential type hints

import scala.language.existentials

val cars = List[(T, Settable[T]) forSome { type T }](

(sedan1, implicitly[Settable[Sedan]]),

(sedan2, implicitly[Settable[Sedan]]),

(sports1, implicitly[Settable[Sports]])

)

Genuine Blog

A Tech Blog by Leo Cheung

Tag Archives: scala generics

A Stateful Calculator In Scala

Cats State

A stateful post-order calculator

Implementation using Scala Cats

Implementing with a plain Scala class

Scala Cats Typeclasses At A Glance

Common typeclass hierarchy

Semigroup and Monoid

SemigroupK and MonoidK

Functor

Monad

Semigroupal and Apply

Applicative

Foldable

Traverse

Example: Applicative and Traverse

Orthogonal Typeclass In Scala

Putting all method implementations in one place

Orthogonal type collection