learning Scalaz: day 5

in

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

On day 4 we reviewed typeclass laws like Functor laws and used ScalaCheck to validate on arbitrary examples of a typeclass. We also looked at three different ways of using Option as Monoid, and looked at Foldable that can foldMap etc.

A fist full of Monads

We get to start a new chapter today on Learn You a Haskell for Great Good.

Monads are a natural extension applicative functors, and they provide a solution to the following problem: If we have a value with context, m a, how do we apply it to a function that takes a normal a and returns a value with a context.

The equivalent is called Monad in Scalaz. Here's the typeclass contract:

trait Monad[F[_]] extends Applicative[F] with Bind[F] { self =>
  ////
}

It extends Applicative and Bind. So let's look at Bind.

Bind

Here's Bind's contract:

trait Bind[F[_]] extends Apply[F] { self =>
  /** Equivalent to `join(map(fa)(f))`. */
  def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
}

And here are the operators:

/** Wraps a value `self` and provides methods related to `Bind` */
trait BindOps[F[_],A] extends Ops[F[A]] {
  implicit def F: Bind[F]
  ////
  import Liskov.<~<
 
  def flatMap[B](f: A => F[B]) = F.bind(self)(f)
  def >>=[B](f: A => F[B]) = F.bind(self)(f)
  def[B](f: A => F[B]) = F.bind(self)(f)
  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(_))
  def >>[B](b: F[B]): F[B] = F.bind(self)(_ => b)
  def ifM[B](ifTrue: => F[B], ifFalse: => F[B])(implicit ev: A <~< Boolean): F[B] = {
    val value: F[Boolean] = Liskov.co[F, A, Boolean](ev)(self)
    F.ifM(value, ifTrue, ifFalse)
  }
  ////
}

It introduces flatMap operator and its symbolic aliases >>= and . We'll worry about the other operators later. We are use to flapMap from the standard library:

scala> 3.some flatMap { x => (x + 1).some }
res2: Option[Int] = Some(4)
 
scala> (none: Option[Int]) flatMap { x => (x + 1).some }
res3: Option[Int] = None

Monad

Back to Monad:

trait Monad[F[_]] extends Applicative[F] with Bind[F] { self =>
  ////
}

Unlike Haskell, Monad[F[_]] exntends Applicative[F[_]] so there's no return vs pure issues. They both use point.

scala> Monad[Option].point("WHAT")
res5: Option[String] = Some(WHAT)
 
scala> 9.some flatMap { x => Monad[Option].point(x * 10) }
res6: Option[Int] = Some(90)
 
scala> (none: Option[Int]) flatMap { x => Monad[Option].point(x * 10) }
res7: Option[Int] = None

Walk the line

LYAHFGG:

Let's say that [Pierre] keeps his balance if the number of birds on the left side of the pole and on the right side of the pole is within three. So if there's one bird on the right side and four birds on the left side, he's okay. But if a fifth bird lands on the left side, then he loses his balance and takes a dive.

Now let's try implementing Pole example from the book.

scala> type Birds = Int
defined type alias Birds
 
scala> case class Pole(left: Birds, right: Birds)
defined class Pole

I don't think it's common to alias Int like this in Scala, but we'll go with the flow. I am going to turn Pole into a case class so I can implement landLeft and landRight as methods:

scala> case class Pole(left: Birds, right: Birds) {
         def landLeft(n: Birds): Pole = copy(left = left + n)
         def landRight(n: Birds): Pole = copy(right = right + n) 
       }
defined class Pole

I think it looks better with some OO:

scala> Pole(0, 0).landLeft(2)
res10: Pole = Pole(2,0)
 
scala> Pole(1, 2).landRight(1)
res11: Pole = Pole(1,3)
 
scala> Pole(1, 2).landRight(-1)
res12: Pole = Pole(1,1)

We can chain these too:

scala> Pole(0, 0).landLeft(1).landRight(1).landLeft(2)
res13: Pole = Pole(3,1)
 
scala> Pole(0, 0).landLeft(1).landRight(4).landLeft(-1).landRight(-2)
res15: Pole = Pole(0,2)

As the book says, an intermediate value have failed but the calculation kept going. Now let's introduce failures as Option[Pole]:

scala> case class Pole(left: Birds, right: Birds) {
         def landLeft(n: Birds): Option[Pole] = 
           if (math.abs((left + n) - right) < 4) copy(left = left + n).some
           else none
         def landRight(n: Birds): Option[Pole] =
           if (math.abs(left - (right + n)) < 4) copy(right = right + n).some
           else none
       }
defined class Pole
 
 
scala> Pole(0, 0).landLeft(2)
res16: Option[Pole] = Some(Pole(2,0))
 
scala> Pole(0, 3).landLeft(10)
res17: Option[Pole] = None

Let's try the chaining using flatMap:

scala> Pole(0, 0).landRight(1) flatMap {_.landLeft(2)}
res18: Option[Pole] = Some(Pole(2,1))
 
scala> (none: Option[Pole]) flatMap {_.landLeft(2)}
res19: Option[Pole] = None
 
scala> Monad[Option].point(Pole(0, 0)) flatMap {_.landRight(2)} flatMap {_.landLeft(2)} flatMap {_.landRight(2)}
res21: Option[Pole] = Some(Pole(2,4))

Note the use of Monad[Option].point(...) here to start the initial value in Option context. We can also try the >>= alias to make it look more monadic:

scala> Monad[Option].point(Pole(0, 0)) >>= {_.landRight(2)} >>= {_.landLeft(2)} >>= {_.landRight(2)}
res22: Option[Pole] = Some(Pole(2,4))

Let's see if monadic chaining simlulates the pole balancing better:

scala> Monad[Option].point(Pole(0, 0)) >>= {_.landLeft(1)} >>= {_.landRight(4)} >>= {_.landLeft(-1)} >>= {_.landRight(-2)}
res23: Option[Pole] = None

It works.

Banana on wire

LYAHFGG:

We may also devise a function that ignores the current number of birds on the balancing pole and just makes Pierre slip and fall. We can call it banana.

Here's the banana that always fails:

scala> case class Pole(left: Birds, right: Birds) {
         def landLeft(n: Birds): Option[Pole] = 
           if (math.abs((left + n) - right) < 4) copy(left = left + n).some
           else none
         def landRight(n: Birds): Option[Pole] =
           if (math.abs(left - (right + n)) < 4) copy(right = right + n).some
           else none
         def banana: Option[Pole] = none
       }
defined class Pole
 
scala> Monad[Option].point(Pole(0, 0)) >>= {_.landLeft(1)} >>= {_.banana} >>= {_.landRight(1)}
res24: Option[Pole] = None

LYAHFGG:

Instead of making functions that ignore their input and just return a predetermined monadic value, we can use the >> function.

Here's how >> behaves with Option:

scala> (none: Option[Int]) >> 3.some
res25: Option[Int] = None
 
scala> 3.some >> 4.some
res26: Option[Int] = Some(4)
 
scala> 3.some >> (none: Option[Int])
res27: Option[Int] = None

Let's try replacing banana with >> (none: Option[Pole]):

scala> Monad[Option].point(Pole(0, 0)) >>= {_.landLeft(1)} >> (none: Option[Pole]) >>= {_.landRight(1)}
<console>:26: error: missing parameter type for expanded function ((x$1) => x$1.landLeft(1))
              Monad[Option].point(Pole(0, 0)) >>= {_.landLeft(1)} >> (none: Option[Pole]) >>= {_.landRight(1)}
                                                   ^

The type inference broke down all the sudden. The problem is likely the operator precedence. Programming in Scala says:

The one exception to the precedence rule, alluded to above, concerns assignment operators, which end in an equals character. If an operator ends in an equals character (=), and the operator is not one of the comparison operators <=, >=, ==, or !=, then the precedence of the operator is the same as that of simple assignment (=). That is, it is lower than the precedence of any other operator.

Note: The above description is incomplete. Another exception from the assignment operator rule is if it starts with (=) like ===.

Because >>= (bind) ends in equals character, its precedence is the lowest, which forces ({_.landLeft(1)} >> (none: Option[Pole])) to evaluate first. There are a few unpalatable work arounds. First we can use dot-and-parens like normal method calls:

scala> Monad[Option].point(Pole(0, 0)).>>=({_.landLeft(1)}).>>(none: Option[Pole]).>>=({_.landRight(1)})
res9: Option[Pole] = None

Or recognize the precedence issue and place parens around just the right place:

scala> (Monad[Option].point(Pole(0, 0)) >>= {_.landLeft(1)}) >> (none: Option[Pole]) >>= {_.landRight(1)}
res10: Option[Pole] = None

Both yield the right result. By the way, changing >>= to flatMap is not going to help since >> still has higher precedence.

for syntax

LYAHFGG:

Monads in Haskell are so useful that they got their own special syntax called do notation.

First, let write the nested lambda:

scala> 3.some >>= { x => "!".some >>= { y => (x.shows + y).some } }
res14: Option[String] = Some(3!)

By using >>=, any part of the calculation can fail:

scala> 3.some >>= { x => (none: Option[String]) >>= { y => (x.shows + y).some } }
res17: Option[String] = None
 
scala> (none: Option[Int]) >>= { x => "!".some >>= { y => (x.shows + y).some } }
res16: Option[String] = None
 
scala> 3.some >>= { x => "!".some >>= { y => (none: Option[String]) } }
res18: Option[String] = None

Instead of the do notation in Haskell, Scala has for syntax, which does the same thing:

scala> for {
         x <- 3.some
         y <- "!".some
       } yield (x.shows + y)
res19: Option[String] = Some(3!)

LYAHFGG:

In a do expression, every line that isn't a let line is a monadic value.

I think this applies true for Scala's for syntax too.

Pierre returns

LYAHFGG:

Our tightwalker's routine can also be expressed with do notation.

scala> def routine: Option[Pole] =
         for {
           start <- Monad[Option].point(Pole(0, 0))
           first <- start.landLeft(2)
           second <- first.landRight(2)
           third <- second.landLeft(1)
         } yield third
routine: Option[Pole]
 
scala> routine
res20: Option[Pole] = Some(Pole(3,2))

We had to extract third since yield expects Pole not Option[Pole].

LYAHFGG:

If we want to throw the Pierre a banana peel in do notation, we can do the following:

scala> def routine: Option[Pole] =
         for {
           start <- Monad[Option].point(Pole(0, 0))
           first <- start.landLeft(2)
           _ <- (none: Option[Pole])
           second <- first.landRight(2)
           third <- second.landLeft(1)
         } yield third
routine: Option[Pole]
 
scala> routine
res23: Option[Pole] = None

Pattern matching and failure

LYAHFGG:

In do notation, when we bind monadic values to names, we can utilize pattern matching, just like in let expressions and function parameters.

scala> def justH: Option[Char] =
         for {
           (x :: xs) <- "hello".toList.some
         } yield x
justH: Option[Char]
 
scala> justH
res25: Option[Char] = Some(h)

When pattern matching fails in a do expression, the fail function is called. It's part of the Monad type class and it enables failed pattern matching to result in a failure in the context of the current monad instead of making our program crash.

scala> def wopwop: Option[Char] =
         for {
           (x :: xs) <- "".toList.some
         } yield x
wopwop: Option[Char]
 
scala> wopwop
res28: Option[Char] = None

The failed pattern matching returns None here. This is an interesting aspect of for syntax that I haven't thought about, but totally makes sense.

List Monad

LYAHFGG:

On the other hand, a value like [3,8,9] contains several results, so we can view it as one value that is actually many values at the same time. Using lists as applicative functors showcases this non-determinism nicely.

Let's look at using List as Applicatives again (This notation might require Scalaz 7.0.0-M3):

scala> ^(List(1, 2, 3), List(10, 100, 100)) {_ * _}
res29: List[Int] = List(10, 100, 100, 20, 200, 200, 30, 300, 300)

let's try feeding a non-deterministic value to a function:

scala> List(3, 4, 5) >>= {x => List(x, -x)}
res30: List[Int] = List(3, -3, 4, -4, 5, -5)

So in this monadic view, List context represent mathematical value that could have multiple solutions. Other than that manipulating Lists using for notation is just like plain Scala:

scala> for {
         n <- List(1, 2)
         ch <- List('a', 'b')
       } yield (n, ch)
res33: List[(Int, Char)] = List((1,a), (1,b), (2,a), (2,b))

MonadPlus and the guard function

Scala's for notation allows filtering:

scala> for {
         x <- 1 |-> 50 if x.shows contains '7'
       } yield x
res40: List[Int] = List(7, 17, 27, 37, 47)

LYAHFGG:

The MonadPlus type class is for monads that can also act as monoids.

Here's the typeclass contract for MonadPlus:

trait MonadPlus[F[_]] extends Monad[F] with ApplicativePlus[F] { self =>
  ...
}

Plus, PlusEmpty, and ApplicativePlus

It extends ApplicativePlus:

trait ApplicativePlus[F[_]] extends Applicative[F] with PlusEmpty[F] { self =>
  ...
}

And that extends PlusEmpty:

trait PlusEmpty[F[_]] extends Plus[F] { self =>
  ////
  def empty[A]: F[A]
}

And that extends Plus:

trait Plus[F[_]]  { self =>
  def plus[A](a: F[A], b: => F[A]): F[A]
}

Similar to Semigroup[A] and Monoid[A], Plus[F[_]] and PlusEmpty[F[_]] requires theier instances to implement plus and empty, but at the type constructor ( F[_]) level.

Plus introduces <+> operator to append two containers:

scala> List(1, 2, 3) <+> List(4, 5, 6)
res43: List[Int] = List(1, 2, 3, 4, 5, 6)

MonadPlus again

MonadPlus introduces filter operation.

scala> (1 |-> 50) filter { x => x.shows contains '7' }
res46: List[Int] = List(7, 17, 27, 37, 47)

A knight's quest

LYAHFGG:

Here's a problem that really lends itself to being solved with non-determinism. Say you have a chess board and only one knight piece on it. We want to find out if the knight can reach a certain position in three moves.

Instead of type aliasing a pair, let's make this into a case class again:

scala> case class KnightPos(c: Int, r: Int)
defined class KnightPos

Heres the function to calculate all of his next next positions:

scala> case class KnightPos(c: Int, r: Int) {
         def move: List[KnightPos] =
           for {
             KnightPos(c2, r2) <- List(KnightPos(c + 2, r - 1), KnightPos(c + 2, r + 1),
               KnightPos(c - 2, r - 1), KnightPos(c - 2, r + 1),
               KnightPos(c + 1, r - 2), KnightPos(c + 1, r + 2),
               KnightPos(c - 1, r - 2), KnightPos(c - 1, r + 2)) if (
               ((1 |-> 8) contains c2) && ((1 |-> 8) contains r2))
           } yield KnightPos(c2, r2)
       }
defined class KnightPos
 
scala> KnightPos(6, 2).move
res50: List[KnightPos] = List(KnightPos(8,1), KnightPos(8,3), KnightPos(4,1), KnightPos(4,3), KnightPos(7,4), KnightPos(5,4))
 
scala> KnightPos(8, 1).move
res51: List[KnightPos] = List(KnightPos(6,2), KnightPos(7,3))

The answers look good. Now we implement chaining this three times:

scala> case class KnightPos(c: Int, r: Int) {
         def move: List[KnightPos] =
           for {
             KnightPos(c2, r2) <- List(KnightPos(c + 2, r - 1), KnightPos(c + 2, r + 1),
             KnightPos(c - 2, r - 1), KnightPos(c - 2, r + 1),
             KnightPos(c + 1, r - 2), KnightPos(c + 1, r + 2),
             KnightPos(c - 1, r - 2), KnightPos(c - 1, r + 2)) if (
             ((1 |-> 8) element c2) && ((1 |-> 8) contains r2))
           } yield KnightPos(c2, r2)
         def in3: List[KnightPos] =
           for {
             first <- move
             second <- first.move
             third <- second.move
           } yield third
         def canReachIn3(end: KnightPos): Boolean = in3 contains end
       }
defined class KnightPos
 
scala> KnightPos(6, 2) canReachIn3 KnightPos(6, 1)
res56: Boolean = true
 
scala> KnightPos(6, 2) canReachIn3 KnightPos(7, 3)
res57: Boolean = false

Monad laws

Left identity

LYAHFGG:

The first monad law states that if we take a value, put it in a default context with return and then feed it to a function by using >>=, it's the same as just taking the value and applying the function to it.

To put this in Scala,

// (Monad[F].point(x) flatMap {f}) assert_=== f(x)
 
scala> (Monad[Option].point(3) >>= { x => (x + 100000).some }) assert_=== 3 |> { x => (x + 100000).some }

Right identity

The second law states that if we have a monadic value and we use >>= to feed it to return, the result is our original monadic value.

// (m forMap {Monad[F].point(_)}) assert_=== m
 
scala> ("move on up".some flatMap {Monad[Option].point(_)}) assert_=== "move on up".some

Associativity

The final monad law says that when we have a chain of monadic function applications with >>=, it shouldn't matter how they're nested.

// (m flatMap f) flatMap g assert_=== m flatMap { x => f(x) flatMap {g} }
 
scala> Monad[Option].point(Pole(0, 0)) >>= {_.landRight(2)} >>= {_.landLeft(2)} >>= {_.landRight(2)}
res76: Option[Pole] = Some(Pole(2,4))
 
scala> Monad[Option].point(Pole(0, 0)) >>= { x =>
       x.landRight(2) >>= { y =>
       y.landLeft(2) >>= { z =>
       z.landRight(2)
       }}}
res77: Option[Pole] = Some(Pole(2,4))

Scalaz 7 expresses these laws as the following:

  trait MonadLaw extends ApplicativeLaw {
    /** Lifted `point` is a no-op. */
    def rightIdentity[A](a: F[A])(implicit FA: Equal[F[A]]): Boolean = FA.equal(bind(a)(point(_: A)), a)
    /** Lifted `f` applied to pure `a` is just `f(a)`. */
    def leftIdentity[A, B](a: A, f: A => F[B])(implicit FB: Equal[F[B]]): Boolean = FB.equal(bind(point(a))(f), f(a))
    /**
     * As with semigroups, monadic effects only change when their
     * order is changed, not when the order in which they're
     * combined changes.
     */
    def associativeBind[A, B, C](fa: F[A], f: A => F[B], g: B => F[C])(implicit FC: Equal[F[C]]): Boolean =
      FC.equal(bind(bind(fa)(f))(g), bind(fa)((a: A) => bind(f(a))(g)))
  }

Here's how to check if Option conforms to the Monad laws. Run sbt test:console with build.sbt we used in day 4:

scala> monad.laws[Option].check
+ monad.applicative.functor.identity: OK, passed 100 tests.
+ monad.applicative.functor.associative: OK, passed 100 tests.
+ monad.applicative.identity: OK, passed 100 tests.
+ monad.applicative.composition: OK, passed 100 tests.
+ monad.applicative.homomorphism: OK, passed 100 tests.
+ monad.applicative.interchange: OK, passed 100 tests.
+ monad.right identity: OK, passed 100 tests.
+ monad.left identity: OK, passed 100 tests.
+ monad.associativity: OK, passed 100 tests.

Looking good, Option. We'll pick it up from here.