Introduction to Functional Programming

James Earl Douglas

April 25, 2021

Agenda

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
    else a.foldRight(Stream[A]())((head, tail) => Cons(head, tail))
}

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
        case Cons(head, tail) => Cons(f(head), map(tail)(f))
      }
  }

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 {
  implicit class MonadOps[F[_]: Monad, A](fa: F[A]) {
    def flatMap[B](f: A => F[B]): F[B] =
      implicitly[Monad[F]].flatMap(fa)(f)
  }
  implicit class MonadConstructor[A](a: A) {
    def pure[F[_]: Monad]: F[A] =
      implicitly[Monad[F]].pure(a)
  }
}

Monad[Option]

Write a Monad implementation for Option.

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

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

Monad[Option]

implicit lazy val myOptionMonad: Monad[Option] =
  new 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
  import Monad.MonadOps
  for {
    x <- Either.right[String, Int](6)
    y <- Either.right[String, Int](x * 7)
  } yield y
} === Right(42)

{
  import Functor.FunctorOps
  import Monad.MonadOps
  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] =
  new 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
  import Monad.MonadOps
  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] =
  new 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
        case Cons(head, tail) => concat(f(head), (flatMap(tail)(f)))
      }
  }

Reader

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

case class Reader[-E, +A](run: E => A)
{
  import Functor.FunctorOps
  import Monad.MonadOps
  {
    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, ɑ] })#λ] =
  new Monad[({ type λ[ɑ] = Reader[E, ɑ] })#λ] {
    override def pure[A](a: A): Reader[Any, A] = Reader(_ => a)
    override def flatMap[A, B](fa: Reader[E, A])(f: A => Reader[E, B]): Reader[E, B] =
      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
  import Monad.MonadOps
  {
    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
  import Monad.MonadOps
  {
    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/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)
template: slides
...