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