# 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
}

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

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)
}

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]

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)``````