Programming Scala with effects

January 08, 2020

This is A Scala port of http://www.cs.nott.ac.uk/~gmh/monads.

Section 1: Abstracting programming patterns

def inc(xs: List[Int]): List[Int] =
  xs match {
    case Nil   => Nil
    case n::ns => (n+1) :: inc(ns)
  }

def sqr(xs: List[Int]): List[Int] =
  xs match {
    case Nil   => Nil
    case n::ns => (n^2) :: sqr(ns)
  }

def map[A,B](f: A => B)(as: List[A]): List[B] =
  as match {
    case Nil   => Nil
    case x::xs => f(x) :: map(f)(xs)
  }

val inc1: List[Int] => List[Int] = map(_+1)
val sqr1: List[Int] => List[Int] = map(_^2)

Section 2: A simple evaluator

sealed trait Expr
case class Val(n: Int) extends Expr
case class Div(x: Expr, y: Expr) extends Expr

def eval(e: Expr): Int =
  e match {
    case Val(n)   => n
    case Div(x,y) => eval(x) / eval(y)
  }

sealed trait Maybe[+A]
case object Nothing extends Maybe[scala.Nothing]
case class Just[A](a: A) extends Maybe[A]

def safediv(n: Int, m: Int): Maybe[Int] =
  if (m == 0) Nothing else Just(n / m)

def eval1(e: Expr): Maybe[Int] =
  e match {
    case Val(n)   => Just(n)
    case Div(x,y) =>
      eval1(x) match {
        case Nothing => Nothing
        case Just(n) =>
          eval1(y) match {
            case Nothing => Nothing
            case Just(m) => safediv(n, m)
          }
      }
  }

def seqn[A,B](ma: Maybe[A], mb: Maybe[B]): Maybe[(A,B)] =
  (ma,mb) match {
    case (Nothing,_)       => Nothing
    case (_,Nothing)       => Nothing
    case (Just(x),Just(y)) => Just((x,y))
  }

def eval2(e: Expr): Maybe[Int] =
  e match {
    case Val(n)   => Just(n)
    case Div(x,y) => val f = (safediv(_,_)).tupled
                     apply(f)(seqn(eval2(x), eval2(y)))
  }

def apply[A,B](f: A => Maybe[B])(ma: Maybe[A]): Maybe[B] =
  ma match {
    case Nothing => Nothing
    case Just(x) => f(x)
  }

case class Op(x: Expr, y: Expr, z: Expr) extends Expr

def eval3(e: Expr): Maybe[Int] =
  e match {
    case Val(n)    => Just(n)
    case Div(x,y)  => val f = (safediv(_,_)).tupled
                      apply(f)(seqn(eval3(x), eval3(y)))
    case Op(x,y,z) => val f: ((Int,(Int,Int))) => Maybe[Int] = ???
                      apply(f)(seqn(eval3(x), seqn(eval3(y), eval3(z))))
  }

Section 3: Combining sequencing and processing

implicit class MaybeBind[A](ma: Maybe[A]) {
  def >>=[B](f: A => Maybe[B]): Maybe[B] =
    ma match {
      case Nothing => Nothing
      case Just(x) => f(x)
    }
}

def eval4(e: Expr): Maybe[Int] =
  e match {
    case Val(n)   => Just(n)
    case Div(x,y) => eval4(x) >>= { n =>
                     eval4(y) >>= { m =>
                     safediv(n, m) }}
  }

implicit class MaybeForComprehension[A](ma: Maybe[A]) {
  def flatMap[B](f: A => Maybe[B]): Maybe[B] =
    ma match {
      case Nothing => Nothing
      case Just(x) => f(x)
    }
  def map[B](f: A => B): Maybe[B] =
    flatMap(f andThen Just.apply)
}

def eval5(e: Expr): Maybe[Int] =
  e match {
    case Val(n)   => Just(n)
    case Div(x,y) => for {
                       n <- eval5(x)
                       m <- eval5(y)
                       q <- safediv(n, m)
                     } yield q
  }

Section 4: Monads in Scala

trait Eq[A] {
  def ===(x: A, y: A): Boolean
  def !==(x: A, y: A): Boolean = !(===(x,y))
}

implicit object BooleanEq extends Eq[Boolean] {
  def ===(x: Boolean, y: Boolean): Boolean = x == y
}

trait Monad[F[_]] {
  def pure[A](a: A): F[A]
  def >>=[A,B](a: F[A])(f: A => F[B]): F[B]
}

implicit class MonadForComprehension[F[_]:Monad,A](fa: F[A]) {
  val M: Monad[F] = implicitly[Monad[F]]
  def flatMap[B](f: A => F[B]): F[B] = M.>>=(fa)(f)
  def map[B](f: A => B): F[B] = M.>>=(fa)(f andThen M.pure)
}

implicit object MonadMaybe extends Monad[Maybe] {
  def pure[A](a: A): Maybe[A] = Just(a)
  def >>=[A,B](a: Maybe[A])(f: A => Maybe[B]): Maybe[B] =
    a match {
      case Nothing => Nothing
      case Just(x) => f(x)
    }
}

Section 5: The list monad

sealed trait LList[+A] {
  def ++[B >: A](xs: LList[B]): LList[B] =
    this match {
      case LNil       => xs
      case LCons(h,t) => LCons(h, t ++ xs)
    }
}
case object LNil extends LList[Nothing]
case class LCons[A](head: A, tail: LList[A]) extends LList[A]

implicit object LListMonad extends Monad[LList] {
  def pure[A](a: A): LList[A] = LCons(a, LNil)
  def >>=[A,B](la: LList[A])(f: A => LList[B]): LList[B] =
    la match {
      case LNil       => LNil
      case LCons(h,t) => f(h) ++ >>=(t)(f)
    }
}

def pairs[A,B](xs: LList[A], ys: LList[B]): LList[(A,B)] =
  for {
    x <- xs
    y <- ys
  } yield (x,y)

Section 6: The state monad