April 25, 2021

# Agenda

• Data structures
• `Option`
• `Either`
• `Stream`
• Combinators
• `Functor`
• `Applicative`
• `Monad`
• Effect systems
• `Reader`

# Verification

Write an extension method that we can use to compare two values of the same type.

``6 * 7 === 42``

# Verification

``````implicit class Eq[A](x: A) {
def ===(y: A): Unit = {
if (x == y) println(s"\u001b[0;32mPass: \${x} == \${y}\u001b[0m")
else System.err.println(s"\u001b[0;31mFail: \${x} != \${y}\u001b[0m")
}
}``````

# Verification

Write another extension method that we can use to contrast two values of the same type.

``6 !== 7``

# Verification

``````implicit class Neq[A](x: A) {
def !==(y: A): Unit = {
if (x != y) println(s"\u001b[0;32mPass: \${x} != \${y}\u001b[0m")
else System.err.println(s"\u001b[0;31mFail: \${x} == \${y}\u001b[0m")
}
}``````

# Verification

We will use these functions to specify and test our code as we go.

# `Option`

Write a sum type that represents optional values.

``````Some(42) === Some(42)
Some(6) !== Some(7)
None === None``````

# `Option`

``````sealed trait Option[+A]
case class Some[A](a: A) extends Option[A]
case object None extends Option[Nothing]``````

# `Option`

Write type-friendly constructors.

``````Option(42) === Some(42)
Option(null) === None
Option() === None``````

# `Option`

``````object Option {
def apply[A](a: A): Option[A] =
if (a == null) None else Some(a)
def apply[A](): Option[A] = None
}``````

# `Either`

Write a sum type that represents values of one or another type.

``````Left(42) === Left(42)
Left(6) !== Left(7)
Right(42) === Right(42)
Right(6) !== Right(7)``````

# `Either`

``````sealed trait Either[L, R]
case class Left[L, R](l: L) extends Either[L, R]
case class Right[L, R](r: R) extends Either[L, R]``````

# `Either`

Write type-friendly constructors.

``````Either.left(42) === Left(42)
Either.left(42) !== Right(42)
Either.right(42) === Right(42)
Either.right(42) !== Left(42)``````

# `Either`

``````object Either {
def left[A, B](a: A): Either[A, B] = Left(a)
def right[A, B](b: B): Either[A, B] = Right(b)
}``````

# `Stream`

Write a sum type that represents a stream of values.

``````Cons(42, Nil) === Cons(42, Nil)
Cons(6, Nil) !== Cons(7, Nil)
Cons(6, Cons(7, Nil)) === Cons(6, Cons(7, Nil))
Nil === Nil``````

# `Stream`

``````sealed trait Stream[+A]
case class Cons[A](head: A, tail: Stream[A]) extends Stream[A]
case object Nil extends Stream[Nothing]``````

# `Stream`

Write type-friendly constructors.

``````Stream(6, 7) === Cons(6, Cons(7, Nil))
Stream(7, 6) !== Cons(6, Cons(7, Nil))
Stream() === Nil``````

# `Stream`

``````object Stream {
def apply[A](): Stream[A] = Nil
def apply[A](a: A*): Stream[A] =
if (a.isEmpty) Nil
}``````

# `Stream`

Write a concatenation function.

``concat(Stream(6), Stream(7)) === Cons(6, Cons(7, Nil))``

# `Stream`

``````def concat[A](x: Stream[A], y: Stream[A]): Stream[A] =
x match {
case Nil => y
case Cons(xh, xt) => Cons(xh, concat(xt, y))
}``````

# `Functor`

Write a `Functor` trait with a curried `map` function.

# `Functor`

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

# `Functor`

Write an extension method for `map`.

# `Functor`

``````object Functor {
implicit class FunctorOps[F[_]: Functor, A](fa: F[A]) {
def map[B](f: A => B): F[B] = implicitly[Functor[F]].map(fa)(f)
}
}``````

# `Functor[Option]`

Write a `Functor` implementation for `Option`.

``````{
import Functor.FunctorOps
for {
x <- Option(6)
y = x * 7
} yield y
} === Some(42)

{
import Functor.FunctorOps
for {
x <- Option[Int]()
y = x * 7
} yield y
} === None``````

# `Functor[Option]`

``````implicit lazy val myOptionFunctor: Functor[Option] =
new Functor[Option] {
override def map[A, B](fa: Option[A])(f: A => B): Option[B] =
fa match {
case Some(a) => Some(f(a))
case None => None
}
}``````

# `Functor[Either]`

Write a right-biased `Functor` implementation for `Either`.

``````{
import Functor.FunctorOps
for {
x <- Either.right[String, Int](6)
y = x * 7
} yield y
} === Right(42)

{
import Functor.FunctorOps
for {
x <- Either.left[String, Int]("nope")
y = x * 7
} yield y
} === Left("nope")``````

# `Functor[Either]`

``````type StringOr[A] = Either[String, A]

implicit lazy val myEitherFunctor: Functor[StringOr] =
new Functor[StringOr] {
override def map[A, B](fa: StringOr[A])(f: A => B): StringOr[B] =
fa match {
case Left(l) => Left(l)
case Right(r) => Right(f(r))
}
}``````

# `Functor[Stream]`

Write a `Functor` implementation for `Stream`.

``````{
import Functor.FunctorOps
for {
x <- Stream(1, 2, 3)
y = x * 2
} yield y
} === Cons(2, Cons(4, Cons(6, Nil)))``````

# `Functor[Stream]`

``````implicit lazy val StreamFunctor: Functor[Stream] =
new Functor[Stream] {
override def map[A, B](fa: Stream[A])(f: A => B): Stream[B] =
fa match {
case Nil => Nil
}
}``````

# `Applicative`

Write a `Applicative` trait with an `ap` function.

# `Applicative`

``````trait Applicative[F[_]] extends Functor[F] {
def pure[A](a: A): F[A]
def ap[A, B](fa: F[A])(f: F[A => B]): F[B]
override def map[A, B](fa: F[A])(f: A => B): F[B] = ap(fa)(pure(f))
}``````

# `Applicative`

Write an extension method for `ap`.

# `Applicative`

``````object Applicative {
implicit class ApplicativeOps[F[_]: Applicative, A](fa: F[A]) {
def ap[B](f: F[A => B]): F[B] = implicitly[Applicative[F]].ap(fa)(f)
}
}``````

# `Applicative[Either]`

Write a right-biased `Applicative` implementation for `Either`.

``````{
import Applicative.ApplicativeOps
Either.right[String, Int](6).ap(
Either.right[String, Int => Int](x => x * 7)
)
} === Right(42)

{
import Applicative.ApplicativeOps
Either.left[String, Int]("nope").ap(
Either.right[String, Int => Int](x => x * 7)
)
} === Left("nope")

{
import Applicative.ApplicativeOps
Either.left[Stream[String], Int](Stream("no")).ap(
Either.left[Stream[String], Int => Int](Stream("way"))
)
} === Left(Cons("no", Cons("way", Nil)))``````

# `Applicative[Either]`

``````type StringsOr[A] = Either[Stream[String], A]

implicit lazy val myEitherApplicative: Applicative[StringsOr] =
new Applicative[StringsOr] {
override def pure[A](a: A): StringsOr[A] = Right(a)
override def ap[A, B](fa: StringsOr[A])(f: StringsOr[A => B]): StringsOr[B] =
fa match {
case Left(fal) =>
f match {
case Left(fl) => Left(concat(fal, fl))
case Right(_) => Left(fal)
}
case Right(far) =>
f match {
case Left(fl) => Left(fl)
case Right(ff) => Right(ff(far))
}
}
}``````

# `Monad`

Write a `Monad` trait with a `pure` function and a curried `flatMap` function.

# `Monad`

``````trait Monad[F[_]] extends Applicative[F] {
def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
override def ap[A, B](fa: F[A])(f: F[A => B]): F[B] =
flatMap(fa)(a => flatMap(f)(k => pure(k(a))))
}``````

# `Monad`

Write extension methods for `pure` and `flatMap`.

# `Monad`

``````object Monad {
def flatMap[B](f: A => F[B]): F[B] =
}
}
}``````

# `Monad[Option]`

Write a `Monad` implementation for `Option`.

``````{
import Functor.FunctorOps
for {
x <- Option(6)
y <- Option(x * 7)
} yield y
} === Some(42)

{
import Functor.FunctorOps
for {
x <- Option(6)
y <- Option[Int]()
} yield y
} === None``````

# `Monad[Option]`

``````implicit lazy val myOptionMonad: Monad[Option] =
override def pure[A](a: A): Option[A] = Some(a)
override def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] =
fa match {
case Some(a) => f(a)
case None => None
}
}``````

# `Monad[Either]`

Write a right-biased `Monad` implementation for `Either`.

``````{
import Functor.FunctorOps
for {
x <- Either.right[String, Int](6)
y <- Either.right[String, Int](x * 7)
} yield y
} === Right(42)

{
import Functor.FunctorOps
for {
x <- Either.right[String, Int](6)
y <- Either.left[String, Int]("nope")
} yield y
} === Left("nope")``````

# `Monad[Either]`

``````implicit lazy val myEitherMonad: Monad[StringOr] =
override def pure[A](a: A): StringOr[A] = Right(a)
override def flatMap[A, B](fa: StringOr[A])(f: A => StringOr[B]): StringOr[B] =
fa match {
case Left(l) => Left(l)
case Right(r) => f(r)
}
}``````

# `Monad[Stream]`

Write a `Monad` implementation for `Stream`.

``````{
import Functor.FunctorOps
for {
x <- Stream(1, 2, 3)
y <- Stream(x * 2)
} yield y
} === Cons(2, Cons(4, Cons(6, Nil)))``````

# `Monad[Stream]`

``````implicit lazy val StreamMonad: Monad[Stream] =
override def pure[A](a: A): Stream[A] = Cons(a, Nil)
override def flatMap[A, B](fa: Stream[A])(f: A => Stream[B]): Stream[B] =
fa match {
case Nil => Nil
}
}``````

# `Reader`

Write a `Monad` implementation for `Reader`, which wraps a unary function.

``case class Reader[-E, +A](run: E => A)``
``````{
import Functor.FunctorOps
{
for {
x <- Reader { env: Map[String, String] => env("X").toInt }
y <- Reader { env: Map[String, String] => env("Y").toInt }
} yield x * y
}.run(sys.env)
} === 42``````

# `Monad[Reader]`

``````implicit def readerMonad[E]: Monad[({ type λ[ɑ] = Reader[E, ɑ] })#λ] =
Reader { e => f(fa.run(e)).run(e) }
}``````

# `Reader#provide`

Write a `provide` function that applies an environment to a `Reader` instance.

``````{
import Functor.FunctorOps
{
for {
x <- Reader { env: Map[String, String] => env("X").toInt }
y <- Reader { env: Map[String, String] => env("Y").toInt }
} yield x * y
}
.provide(sys.env)
.run(())
} === 42``````

# `Reader#provide`

``````implicit class ReaderProvide[E, A](r: Reader[E, A]) {
def provide(e: E): Reader[Any, A] =
Reader { _ => r.run(e) }
}``````

# `Reader#provideSome`

Write a `provideSome` function that partially applies an environment to a `Reader` instance.

``````trait HasX { def x: String }
trait HasY { def y: String }

{
import Functor.FunctorOps
{
for {
x <- Reader[HasX with HasY, Int] { env: HasX => env.x.toInt }
y <- Reader[HasX with HasY, Int] { env: HasY => env.y.toInt }
} yield x * y
}
.provideSome { hasY: HasY =>
new HasX with HasY {
override val x: String = sys.env("X")
override val y: String = hasY.y
}
}
.provide {
new HasY {
val y: String = sys.env("Y")
}
}
.run(())
} === 42``````

# `Reader#provideSome`

``````implicit class ReaderProvideSome[E, A](r: Reader[E, A]) {
def provideSome[E1](f: E1 => E): Reader[E1, A] =
Reader { e1 => r.run(f(e1)) }
}``````

# Demo

This file is literate Scala, and can be run using Codedown:

``````\$ curl https://earldouglas.com/talks/ifp/slides.md |
codedown scala |
X=6 Y=7 xargs -0 scala -nc -e
Pass: 42 == 42
Pass: 6 != 7
Pass: Some(42) == Some(42)
Pass: Some(6) != Some(7)
Pass: None == None
Pass: Some(42) == Some(42)
Pass: None == None
Pass: None == None
Pass: Left(42) == Left(42)
Pass: Left(6) != Left(7)
...``````