Skip to content

Instantly share code, notes, and snippets.

@davegurnell

davegurnell/notes.md

Last active May 6, 2022 15:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save davegurnell/44862a454bb66903f41560ba118f0612 to your computer and use it in GitHub Desktop.
Save davegurnell/44862a454bb66903f41560ba118f0612 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
notes.md

Scala Course

Dave Pereira-Gurnell

Objectives

Things that enable a "functional style" in Scala:

  • Scala Language Features
  • Higher Level Theory

"Functional style":

  • Modular
  • Composable
  • Statically Typed

Logistics

Clone this:

https://github.com/davegurnell/cats-sandbox

git clone https://github.com/davegurnell/cats-sandbox.git
cd cats-sandbox
sbt
run

Core Scala Patterns

Algebraic Data Types

Use case: Any time you want to model data.

Data type made of a finite "and" or "or" of other data types.

"Product type", aka an "and" type, aka case class.

A colour is:

  • a red value (a double) and
  • a green value (a double) and
  • a blue value (a double) and
case class Color(red: Int, green: Int, blue: Int)

"Sum type", aka an "or" type, aka a sealed trait!

A shape is either:

  • a rectangle or
  • a circle
sealed trait Shape
case class Rect(w: Double, h: Double) extends Shape
case class Circle(radius: Double) extends Shape

A JSON value is:

  • a JSON object OR
  • a JSON array OR
  • a JSON string OR
  • a JSON number OR
  • a JSON boolean OR
  • a JSON null value
sealed trait Json
case class JsonObject(fields: Map[String, Json]) extends Json
case class JsonArray(items: List[Json]) extends Json
case class JsonString(value: String) extends Json
case class JsonNumber(value: Double) extends Json
case class JsonBoolean(value: Boolean) extends Json
case object JsonNull extends Json

Structural Recursion / Pattern Matching

Use this pattern to write code to operate on an ADT.

Two ways of doing this in Scala:

  • Pattern matching
  • Write a method on the ADT

Example:

  • Write a method to calculate the area of a shape
  • Write a method to calculate the perimeter of a shape
sealed trait Shape {
  def area: Double

  def perimeter: Double =
    this match {
      case Rect(w, h) => 2 * w + 2 * h
      case Circle(r) => 2 * math.Pi * r
    }
}

case class Rect(w: Double, h: Double) extends Shape {
  def area: Double =
    w * h
}

case class Circle(radius: Double) extends Shape {
  def area: Double =
    math.Pi * radius * radius
}

Exercises:

  1. Write a stringify method for your Json data type. Example use case:

    myJsonValue.stringify // => "{ "field": "value" }"

    TIP: Here's how you can "escape" a Scala string:

    def escape(str: String): String =
  "\"" + str.replaceAll("\"", "\\\\\"") + "\""

  2. Write a method getField that retrieves any JSON value given its name:

    • What should the method do if the field is not found?
    • What should the method do if you don't have a JSON object?

Extension Methods

Use case: You want to add a method to an existing type, but you can't (or don't want to) edit the source code of the type.

object Times10Syntax {
  implicit class Times10Thing(value: Int) {
    def times10: Int =
      value * 10
  }
}

object MyApplicationCode extends App {
  import Times10Syntax._

  println(123.times10)
}

Type Classes

They are:

  • A pattern for associating implementations with types.
  • A pattern for looking up an implemention given a type.

Use them when:

  • We have a behaviour we want to associate with manyy different types.
  • We don't necessarily own the code for those types (or we don't want to change it).
  • We want to look up an implement based on a type.

A type class has three elements:

  1. "Type Class" -- A trait to describe some behaviour ("the type class"). This always has a single type parameter.

    trait CsvEncoder[A] {
  def encode(value: A): List[String]
}

  2. "Type Class Instances" -- A set of "type class instances": implementations of that trait for different "target types"

    implicit val personEncoder: CsvEncoder[Person] =
  new CsvEncoder[Person] {
    def encode(p: Person): List[String] =
      List(p.name, p.age.toString)
  }

implicit val booleanEncoder: CsvEncoder[Boolean] =
  new CsvEncoder[Boolean] {
    def encode(b: Boolean): List[String] =
      List(b.toString)
  }

  3. "Interface Methods" -- Some kind of function that looks up instances of the type class by type

    def csvify[A](value: A)(implicit enc: CsvEncoder[A]): List[String] =
  enc.encode(value)

Implicit resolution rules

  • Must have implicit keyword
  • Resolved by type (names of vals are unimportant)
  • Must not be ambiguous
  • Must be in "implicit scope"

Implicit scope

  • The compiler looks for any implicit vals that are "in implicit scope" at the call site
  • Implicit scope is:
    • Normal scope (imports, local definitions, anything inherited)
    • Plus anything in the companion objects of the types being searched for
    • So if the compiler is searching for JsonEncoder[Person], it searches the companion objects for JsonEncoder and Person
  • This means:
    • Put companion objects for really common types (string, int, etc) in the companion object for the type class (e.g. JsonEncoder)
    • Put companion objects for "business" data types (e.g. Person) in the companion object for the target type

Implicit chaining

The compiler can use:

  • implicit vals (see JsonEncoder.booleanEncoder as an example)
  • or implicit defs where all the parameters are implicit (see JsonEncoder.listEncoder as an example)

The compiler can chain these defs and vals together to produce arbitrarily complex type class instances.

Adding Things Up! (An Example of a Type Class)

Cats provides a couple of type classes for "adding things up":

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

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

We can use these as follows:

// Import the |+| operator
// and instances of Semigroup and Monoid
// for lots of stdlib types:
import cats.implicits._

// We can use |+| to add values of any type
// that we have a Semigroup or Monoid for:
1 |+| 2
"a" |+| "b"
List(1, 2) |+| List(3, 4)
("a", 1) |+| ("b", 2)
Option(("a", 1)) |+| Option(("b", 2))
Map("a" -> 1, "b" -> 2) |+| Map("b" -> 3, "c" -> 4)
// etc...

// We can use combineAll to sum the values
// in a list, provided we have a Monoid
// for the value type:
List(1, 2, 3).combineAll
List("a", "b").combineAll
List(List(1, 2), List(3, 4)).combineAll
// etc...

Structure of Cats

  • package cats -- all the type classes

    import cats.Monoid

  • package cats.instances -- all the instances of those type classes, organised by "target type"

    import cats.instances.option._
import cats.instances.string._

  • package cats.syntax -- all the extension methods for all those type classes, organised by type class

    import cats.syntax.monoid._

  • kitchen sink import -- all of the instances and all of the syntax -- USE THIS!

    import cats.implicits._

Decomposing Problems using Functions

Let's solve a problem using top-down decomposition. The problem is reading/validating a Map[String, String] and turning it into a value of case class:

Map("name" -> "Dave", "age" -> "43", "house" -> "123", "street" -> "FP Avenue") // => Person("Dave", 43, Address(123, "FP Avenue"))

Map("age" -> "-43", "house" -> "a", "street" -> "    ") // => fail gracefully with an error

Start by writing a method header. Decide on the type signature. Stub out the body of the method with a ???.

One of the key observations here is that reading/validating the data can fail. To model this we introduce an Either in the return type (we could also use Option):

def readPerson(data: Map[String, String]): Either[String, Person] =
  ???

Now stub out the method body using pseudocode:

def readPerson(data: Map[String, String]): Either[String, Person] =
  // get hold of the name as a string
  // get hold of the age as an int
  // get hold of the address
  // combine them
  ???

For each step, if it's not obvious how to write it in one line, create another method and repeat the process. Determine the type signature, stub out the body with ???, and start writing more pseudocode!

def readName(data: Map[String, String]): Either[String, String] =
  // get the name from the map
  // trim the string
  // check it's non-blank
  ???

def readAge(data: Map[String, String]): Either[String, Int] =
  getValueFromMap(data, "age") // Either[String, String]
    .flatMap(turnValueIntoInt) // String => Either[String, Int]

def getValueFromMap(data: Map[String, String], name: String): Either[String, String] =
  ???

def turnValueIntoInt(value: String): Either[String, Int] =
  ???

Monads, Applicatives, Functors, Oh My!

There are three super-important type classes for sequencing stuff:

  • Functor:

    • gives us map:

      F[A].map(A => B) => F[B]

    • for sequencing non-effectful computations (type A => B rather than A => F[B]) along a "happy path"

  • Applicative:

    • gives us pure and product (and the higher-level syntactic sugar, mapN)

      pure(A) => F[A] product(F[A], F[B]) => F[(A, B)] (F[A], F[B], ...).mapN((A, B, ...) => R) => F[R]

    • for combining the results of independent effectful computations

    • extends Functor, so we also get map

  • Monad:

    • gives us flatMap:

      F[A].flatMap(A => F[B]) => F[B]

      • for sequencing effectful computations (where each step returns a new F[...])
      • extends Applicative, so we also get map, pure, product, and mapN

Monads

Monad is the most "powerful" of these type classes. However, it's also the most restrictive. All relevant methods (map, product, mapN, etc) are implemented in terms of flatMap, so they all involve sequences of steps, one after the other. This means:

  • we can't do things in parallel (e.g. with the IO monad from Cats Effect);
  • we can't accumulate errors (e.g. with Either)

Applicatives

Applicative functors are less "powerful" than monads because they don't provide flatMap. However, they're also less constrained because they don't have to define other methods in terms of it.

Hence we can have data types like Validated, which is structurally similar to Either but has methods that allow us to accumulate errors.

Aside: It's worth noting that, while we often think of a data type like Either as being a monad, the data structure and the type class are actually two different things. We tend to conflate the two because in Scala, the common idiom is to look stuff up by type (e.g. Applicative.apply[Either[String, *]]). Because of this, our understanding is biased towards having one canonical interpretation of Either as a monad.

Parallel

Either gives us fail-fast monadic error handling. Validated gives us cumulative error handling. It's annoying having to choose/convert between the two types to get different semantics.

Fortunately, Cats has a type class called Parallel that automates the conversion. Often there are pairings of convenient monads and equivalent applicatives. Parallel represents these relationships.

For example, there is an instance of Parallel that associates Either (fail-fast error handling) with Validated (cumulative error handling). There's also an instance that associates IO (sequential async computation) with a second type for concurrent async computation (called IO.Par).

Cats provides "parallel" versions of various applicative methods that work with monads instead:

(either1, either2, either3).parMapN(function)
(either1, either2, either3).parTupled
listOfEithers.parSequence
listOfValues.parTraverse(function)

In each case, the parFoo method converts the monad to its equivalent applicative, calls the corresponding applicative method to do the sequencing (parMapN calls mapN etc), and converts the result back to a monad.

Boom! No need to use Validated ever again!

Kleisli

Kleislis are tools for composing monadic functions.

A Kleisli[F, A, B] is a wrapper for a function of type A => F[B]. It's defined like this:

case class Kleisli[F[_], A, B](run: A => F[B]) {
  // lots of cool methods
}

It provides a handy andThen method for sequencing two monadic functions (just as the built-in andThen method does for non-monadic functions).

It also supports composition using mapN, parMapN, and so on. See FormDataDecoder.scala for examples.

Next Up!

  • [xxxx] Invariant and Contravariant functors!
  • [xxxx] Traverse and Foldable (traverse and sequence methods)
  • [xxxxxx] When to invent your own monad? (or when to re-use a built-in one)
  • [xx] Why is Semigroupal called Semigroupal (and wtf is a Semigroupal)
  • [xxx] Define an Applicative instance for Either!
  • What's MonadError?!
  • Writing code that works with ANY monad!

Invariant and Contravariant Functors

Normal functors can also be called "covariant functors". The represent wrapped values or wrapped functions that return values.

Option[A]
JsonDecoder[A]

We can map over a normal functor:

F[A].map(A => B) => F[B]

Example:

trait JsonDecoder[A] {
  def decode(json: Json): Either[String, A]

  def map[B](func: A => B): JsonDecoder[B] = {
    val self = this
    new JsonDecoder[B] {
      def decode(json: Json): Either[String, B] =
        self.decode(json).map(func)
    }
  }
}

Contravariant functors wrap functions that consume values:

JsonEncoder[A] // like a function A => Json
Ordering[A] // like a function (A, A) => Int

We can't map over JsonEncoder, but we can do the opposite -- contramap:

// Note the function is from B to A, not A to B:
F[A].contramap(B => A) => F[B]

Example:

trait JsonEncoder[A] {
  def encode(a: A): Json

  def contramap[B](func: B => A): JsonEncoder[B] =
    val self = this
    new JsonEncoder[B] {
      def encode(b: B): Json =
        self.encode(func(b))
    }
}

There are also invariant functors, which represent functions that consume and return values of type A:

F[A].imap(B => A)(A => B) => F[B]

Monoids are a great example. We can create a Monoid[Currency] in terms of a Monoid[Int]. It has to:

  • Turn the Currencies into Ints
  • Add the Ints
  • Turn the result back into a Currency
implicit val currencyMonoid: Monoid[Currency] =
  Monoid[Int].imap(currencyToInt)(intToCurrency) // => Monoid[Currency]

Traverse and Sequence

Cats gives you two methods to traverse lists of applicatives (or, by association, lists of monads):

// F[...] is a sequence type: List, Vector, Stream, Chain, etc
//        aka a type that has an instance of the Traverse type class
// G[...] is an applicative
//        aka a type that has an instance of the Applicative type class

F[G[A]].sequence => G[F[A]]
F[A].traverse(A => G[B]) => G[F[B]]

Most important thing: traverse is equivalent to map then sequence:

list.map(function).sequence // is equvalent to
list.traverse(function)

There are also parallel variants of these methods!

F[G[A]].parSequence => G[F[A]]
F[A].parTraverse(A => G[B]) => G[F[B]]

list.map(function).parSequence // is equvalent to
list.parTraverse(function)

Further Reading

  • ADTs
    • Chapter 4. Essential Scala
  • map and flatMap
    • Chapter 5. Essential Scala
  • Type Classes
    • Chapter 7. Essential Scala
    • Chapter 1. Scala with Cats
  • Monoids
    • Chapter 2. Scala with Cats
  • Functors
    • Chapter 3. Scala with Cats
  • Monads
    • Chapter 4. Scala with Cats
  • Applicatives and Parallel
    • Chapter 6. Scala with Cats
  • Foldable and Traverse
    • Chapter 7. Scala with Cats

Appendix A. Type Charts

Receiver Method Parameters Result
List[A] map A => B List[B]
List[A] flatMap A => List[B] List[B]
Vector[A] map A => B Vector[B]
Vector[A] flatMap A => Vector[B] Vector[B]
Option[A] map A => B Option[B]
Option[A] flatMap A => Option[B] Option[B]
Either[E, A] map A => B Either[E, B]
Either[E, A] flatMap A => Either[E, B] Either[E, B]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment