learning Scalaz: day 8

in

Hey there. There's an updated html5 book version, if you want.

On day 7 we reviewed Applicative Builder, and looked at State monad, \/ monad, and Validation. Let's continue on.

Some useful monadic functions

Learn You a Haskell for Great Good says:

In this section, we're going to explore a few functions that either operate on monadic values or return monadic values as their results (or both!). Such functions are usually referred to as monadic functions.

In Scalaz Monad extends Applicative, so there's no question that all monads are functors. This means we can use map or <*> operator.

join method

LYAHFGG:

It turns out that any nested monadic value can be flattened and that this is actually a property unique to monads. For this, the join function exists.

In Scalaz join (and its symbolic alias μ) is a method introduced by Bind:

trait BindOps[F[_],A] extends Ops[F[A]] {
  ...
  def join[B](implicit ev: A <~< F[B]): F[B] = F.bind(self)(ev(_))
  def μ[B](implicit ev: A <~< F[B]): F[B] = F.bind(self)(ev(_))
  ...
}

Let's try it out:

scala> (Some(9.some): Option[Option[Int]]).join
res9: Option[Int] = Some(9)
 
scala> (Some(none): Option[Option[Int]]).join
res10: Option[Int] = None
 
scala> List(List(1, 2, 3), List(4, 5, 6)).join
res12: List[Int] = List(1, 2, 3, 4, 5, 6)
 
scala> 9.right[String].right[String].join
res15: scalaz.Unapply[scalaz.Bind,scalaz.\/[String,scalaz.\/[String,Int]]]{type M[X] = scalaz.\/[String,X]; type A = scalaz.\/[String,Int]}#M[Int] = \/-(9)
 
scala> "boom".left[Int].right[String].join
res16: scalaz.Unapply[scalaz.Bind,scalaz.\/[String,scalaz.\/[String,Int]]]{type M[X] = scalaz.\/[String,X]; type A = scalaz.\/[String,Int]}#M[Int] = -\/(boom)

filterM method

LYAHFGG:

The filterM function from Control.Monad does just what we want!
...
The predicate returns a monadic value whose result is a Bool.

In Scalaz filterM is implemented in several places. For List it seems to be there by import Scalaz._.

trait ListOps[A] extends Ops[List[A]] {
  ...
  final def filterM[M[_] : Monad](p: A => M[Boolean]): M[List[A]] = l.filterM(self)(p)
  ...
}

For some reason Vector support needs a nudge:

scala> List(1, 2, 3) filterM { x => List(true, false) }
res19: List[List[Int]] = List(List(1, 2, 3), List(1, 2), List(1, 3), List(1), List(2, 3), List(2), List(3), List())
 
scala> import syntax.std.vector._
import syntax.std.vector._
 
scala> Vector(1, 2, 3) filterM { x => Vector(true, false) }
res20: scala.collection.immutable.Vector[Vector[Int]] = Vector(Vector(1, 2, 3), Vector(1, 2), Vector(1, 3), Vector(1), Vector(2, 3), Vector(2), Vector(3), Vector())

foldLeftM method

LYAHFGG:

The monadic counterpart to foldl is foldM.

In Scalaz, this is implemented in Foldable as foldLeftM. There's also foldRightM too.

scala> def binSmalls(acc: Int, x: Int): Option[Int] = {
         if (x > 9) (none: Option[Int])
         else (acc + x).some
       }
binSmalls: (acc: Int, x: Int)Option[Int]
 
scala> List(2, 8, 3, 1).foldLeftM(0) {binSmalls}
res25: Option[Int] = Some(14)
 
scala> List(2, 11, 3, 1).foldLeftM(0) {binSmalls}
res26: Option[Int] = None

Making a safe RPN calculator

LYAHFGG:

When we were solving the problem of implementing a RPN calculator, we noted that it worked fine as long as the input that it got made sense.

I did not cover that chapter, but the code is here so let's translate it into Scala:

scala> def foldingFunction(list: List[Double], next: String): List[Double] = (list, next) match {
         case (x :: y :: ys, "*") => (y * x) :: ys
         case (x :: y :: ys, "+") => (y + x) :: ys
         case (x :: y :: ys, "-") => (y - x) :: ys
         case (xs, numString) => numString.toInt :: xs
       }
foldingFunction: (list: List[Double], next: String)List[Double]
 
scala> def solveRPN(s: String): Double =
         (s.split(' ').toList.foldLeft(Nil: List[Double]) {foldingFunction}).head
solveRPN: (s: String)Double
 
scala> solveRPN("10 4 3 + 2 * -")
res27: Double = -4.0

Looks like it's working. The next step is to change the folding function to handle errors gracefully. Scalaz adds parseInt to String which returns Validation[NumberFormatException, Int]. We can call toOption on a validation to turn it into Option[Int] like the book:

scala> "1".parseInt.toOption
res31: Option[Int] = Some(1)
 
scala> "foo".parseInt.toOption
res32: Option[Int] = None

Here's the updated folding function:

scala> def foldingFunction(list: List[Double], next: String): Option[List[Double]] = (list, next) match {
         case (x :: y :: ys, "*") => ((y * x) :: ys).point[Option]
         case (x :: y :: ys, "+") => ((y + x) :: ys).point[Option]
         case (x :: y :: ys, "-") => ((y - x) :: ys).point[Option]
         case (xs, numString) => numString.parseInt.toOption map {_ :: xs}
       }
foldingFunction: (list: List[Double], next: String)Option[List[Double]]
 
scala> foldingFunction(List(3, 2), "*")
res33: Option[List[Double]] = Some(List(6.0))
 
scala> foldingFunction(Nil, "*")
res34: Option[List[Double]] = None
 
scala> foldingFunction(Nil, "wawa")
res35: Option[List[Double]] = None

Here's the updated solveRPN:

scala> def solveRPN(s: String): Option[Double] = for {
         List(x) <- s.split(' ').toList.foldLeftM(Nil: List[Double]) {foldingFunction}
       } yield x
solveRPN: (s: String)Option[Double]
 
scala> solveRPN("1 2 * 4 +")
res36: Option[Double] = Some(6.0)
 
scala> solveRPN("1 2 * 4")
res37: Option[Double] = None
 
scala> solveRPN("1 8 garbage")
res38: Option[Double] = None

Composing monadic functions

LYAHFGG:

When we were learning about the monad laws, we said that the <=< function is just like composition, only instead of working for normal functions like a -> b, it works for monadic functions like a -> m b.

Looks like I missed this one too.

Kleisli

In Scalaz there's a special wrapper for function of type A => M[B] called Kleisli:

sealed trait Kleisli[M[+_], -A, +B] { self =>
  def run(a: A): M[B]
  ...
  /** alias for `andThen` */
  def >=>[C](k: Kleisli[M, B, C])(implicit b: Bind[M]): Kleisli[M, A, C] =  kleisli((a: A) => b.bind(this(a))(k(_)))
  def andThen[C](k: Kleisli[M, B, C])(implicit b: Bind[M]): Kleisli[M, A, C] = this >=> k
  /** alias for `compose` */ 
  def <=<[C](k: Kleisli[M, C, A])(implicit b: Bind[M]): Kleisli[M, C, B] = k >=> this
  def compose[C](k: Kleisli[M, C, A])(implicit b: Bind[M]): Kleisli[M, C, B] = k >=> this
  ...
}
 
object Kleisli extends KleisliFunctions with KleisliInstances {
  def apply[M[+_], A, B](f: A => M[B]): Kleisli[M, A, B] = kleisli(f)
}

We can use Kleisli object to construct it:

scala> val f = Kleisli { (x: Int) => (x + 1).some }
f: scalaz.Kleisli[Option,Int,Int] = scalaz.KleisliFunctions$$anon$18@7da2734e
 
scala> val g = Kleisli { (x: Int) => (x * 100).some }
g: scalaz.Kleisli[Option,Int,Int] = scalaz.KleisliFunctions$$anon$18@49e07991

We can then compose the functions using <=<, which runs rhs first like f compose g:

scala> 4.some >>= (f <=< g)
res59: Option[Int] = Some(401)

There's also >=>, which runs lhs first like f andThen g:

scala> 4.some >>= (f >=> g)
res60: Option[Int] = Some(500)

Reader again

As a bonus, Scalaz defines Reader as a special case of Kleisli as follows:

  type ReaderT[F[+_], E, A] = Kleisli[F, E, A]
  type Reader[E, A] = ReaderT[Id, E, A]
  object Reader {
    def apply[E, A](f: E => A): Reader[E, A] = Kleisli[Id, E, A](f)
  }

We can rewrite the reader example from day 6 as follows:

scala> val addStuff: Reader[Int, Int] = for {
         a <- Reader { (_: Int) * 2 }
         b <- Reader { (_: Int) + 10 }
       } yield a + b
addStuff: scalaz.Reader[Int,Int] = scalaz.KleisliFunctions$$anon$18@343bd3ae
 
scala> addStuff(3)
res76: scalaz.Id.Id[Int] = 19

The fact that we are using function as a monad becomes somewhat clearer here.

Making monads

LYAHFGG:

In this section, we're going to look at an example of how a type gets made, identified as a monad and then given the appropriate Monad instance.
...
What if we wanted to model a non-deterministic value like [3,5,9], but we wanted to express that 3 has a 50% chance of happening and 5 and 9 both have a 25% chance of happening?

Since Scala doesn't have a built-in rational, let's just use Double. Here's the case class:

scala> :paste
// Entering paste mode (ctrl-D to finish)
 
case class Prob[A](list: List[(A, Double)])
 
trait ProbInstances {
  implicit def probShow[A]: Show[Prob[A]] = Show.showA
}
 
case object Prob extends ProbInstances
 
// Exiting paste mode, now interpreting.
 
defined class Prob
defined trait ProbInstances
defined module Prob

Is this a functor? Well, the list is a functor, so this should probably be a functor as well, because we just added some stuff to the list.

scala> :paste
// Entering paste mode (ctrl-D to finish)
 
case class Prob[A](list: List[(A, Double)])
 
trait ProbInstances {
  implicit val probInstance = new Functor[Prob] {
    def map[A, B](fa: Prob[A])(f: A => B): Prob[B] =
      Prob(fa.list map { case (x, p) => (f(x), p) })
  }
  implicit def probShow[A]: Show[Prob[A]] = Show.showA
}
 
case object Prob extends ProbInstances
 
scala> Prob((3, 0.5) :: (5, 0.25) :: (9, 0.25) :: Nil) map {-_} 
res77: Prob[Int] = Prob(List((-3,0.5), (-5,0.25), (-9,0.25)))

Just like the book we are going to implement flatten first.

case class Prob[A](list: List[(A, Double)])
 
trait ProbInstances {
  def flatten[B](xs: Prob[Prob[B]]): Prob[B] = {
    def multall(innerxs: Prob[B], p: Double) =
      innerxs.list map { case (x, r) => (x, p * r) }
    Prob((xs.list map { case (innerxs, p) => multall(innerxs, p) }).flatten)
  }
 
  implicit val probInstance = new Functor[Prob] {
    def map[A, B](fa: Prob[A])(f: A => B): Prob[B] =
      Prob(fa.list map { case (x, p) => (f(x), p) })
  }
  implicit def probShow[A]: Show[Prob[A]] = Show.showA
}
 
case object Prob extends ProbInstances

This should be enough prep work for monad:

scala> :paste
// Entering paste mode (ctrl-D to finish)
 
case class Prob[A](list: List[(A, Double)])
 
trait ProbInstances {
  def flatten[B](xs: Prob[Prob[B]]): Prob[B] = {
    def multall(innerxs: Prob[B], p: Double) =
      innerxs.list map { case (x, r) => (x, p * r) }
    Prob((xs.list map { case (innerxs, p) => multall(innerxs, p) }).flatten)
  }
 
  implicit val probInstance = new Functor[Prob] with Monad[Prob] {
    def point[A](a: => A): Prob[A] = Prob((a, 1.0) :: Nil)
    def bind[A, B](fa: Prob[A])(f: A => Prob[B]): Prob[B] = flatten(map(fa)(f)) 
    override def map[A, B](fa: Prob[A])(f: A => B): Prob[B] =
      Prob(fa.list map { case (x, p) => (f(x), p) })
  }
  implicit def probShow[A]: Show[Prob[A]] = Show.showA
}
 
case object Prob extends ProbInstances
 
// Exiting paste mode, now interpreting.
 
defined class Prob
defined trait ProbInstances
defined module Prob

The book says it satisfies the monad laws. Let's implement the Coin example:

scala> :paste
// Entering paste mode (ctrl-D to finish)
 
sealed trait Coin
case object Heads extends Coin
case object Tails extends Coin
implicit val coinEqual: Equal[Coin] = Equal.equalA
 
def coin: Prob[Coin] = Prob(Heads -> 0.5 :: Tails -> 0.5 :: Nil)
def loadedCoin: Prob[Coin] = Prob(Heads -> 0.1 :: Tails -> 0.9 :: Nil)
 
def flipThree: Prob[Boolean] = for {
  a <- coin
  b <- coin
  c <- loadedCoin
} yield { List(a, b, c) all {_ === Tails} }
 
// Exiting paste mode, now interpreting.
 
defined trait Coin
defined module Heads
defined module Tails
coin: Prob[Coin]
loadedCoin: Prob[Coin]
flipThree: Prob[Boolean]
 
scala> flipThree
res81: Prob[Boolean] = Prob(List((false,0.025), (false,0.225), (false,0.025), (false,0.225), (false,0.025), (false,0.225), (false,0.025), (true,0.225)))

So the probability of having all three coins on Tails even with a loaded coin is pretty low.

We will continue from here later.