MonadFilter 

Here’s the typeclass contract for `MonadFilter`:

@typeclass trait MonadFilter[F[_]] extends Monad[F] with FunctorFilter[F] {

  def empty[A]: F[A]

  ...
}

We can use this to get an empty value of a datatype that supports it.

scala> import cats._, cats.data._, cats.implicits._
import cats._
import cats.data._
import cats.implicits._

scala> MonadFilter[List].empty[Int]
res0: List[Int] = List()

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

Here’s the function to calculate all of the knight’s 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 to 8).toList contains c2) && ((1 to 8).toList contains r2))
           } yield KnightPos(c2, r2)
       }
defined class KnightPos

scala> KnightPos(6, 2).move
res1: 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
res2: 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 to 8).toList contains c2) && ((1 to 8).toList 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)
res3: Boolean = true

scala> KnightPos(6, 2) canReachIn3 KnightPos(7, 3)
res4: Boolean = false

As it turns out, from (6, 2) you can reach (6, 1) in three moves, but not (7, 3). As with Pierre’s bird example, one of key aspect of the monadic calculation is that the effect of one move can be passed on to the next.

We’ll pick up from here.