Alternative 

There’s a typeclass that combines Applicative and MonoidK called Alternative:

@typeclass trait Alternative[F[_]] extends Applicative[F] with MonoidK[F] { self =>
   ....
}

Alternative on its own does not introduce any new methods or operators.

It’s more of a weaker (thus better) Applicative version of MonadPlus that adds filter on top of Monad. See day 3 to review the applicative style of coding.

Alternative laws 

trait AlternativeLaws[F[_]] extends ApplicativeLaws[F] with MonoidKLaws[F] {
  implicit override def F: Alternative[F]
  implicit def algebra[A]: Monoid[F[A]] = F.algebra[A]

  def alternativeRightAbsorption[A, B](ff: F[A => B]): IsEq[F[B]] =
    (ff ap F.empty[A]) <-> F.empty[B]

  def alternativeLeftDistributivity[A, B](fa: F[A], fa2: F[A], f: A => B): IsEq[F[B]] =
    ((fa |+| fa2) map f) <-> ((fa map f) |+| (fa2 map f))

  def alternativeRightDistributivity[A, B](fa: F[A], ff: F[A => B], fg: F[A => B]): IsEq[F[B]] =
    ((ff |+| fg) ap fa) <-> ((ff ap fa) |+| (fg ap fa))
}

There’s an open question by Yoshida-san on whether the last law is necessary or not.

Wolf, Goat, Cabbage 

Here’s Justin Le (@mstk)’s 2013 'Wolf, Goat, Cabbage: The List MonadPlus & Logic Problems.'.

We can try implementing this using Alternative.

A farmer has a wolf, a goat, and a cabbage that he wishes to transport across a river. Unfortunately, his boat can carry only one thing at a time with him. He can’t leave the wolf alone with the goat, or the wolf will eat the goat. He can’t leave the goat alone with the cabbage, or the goat will eat the cabbage. How can he properly transport his belongings to the other side one at a time, without any disasters?

scala> import cats._, cats.instances.all._, cats.syntax.show._
import cats._
import cats.instances.all._
import cats.syntax.show._

scala> import cats.syntax.cartesian._, cats.syntax.semigroupk._
import cats.syntax.cartesian._
import cats.syntax.semigroupk._

scala> :paste
// Entering paste mode (ctrl-D to finish)
sealed trait Character
case object Farmer extends Character
case object Wolf extends Character
case object Goat extends Character
case object Cabbage extends Character

case class Move(x: Character)

case class Plan(moves: List[Move])

sealed trait Position
case object West extends Position
case object East extends Position

implicit val moveShow = Show.show[Move](_ match {
  case Move(Farmer)  => "F"
  case Move(Wolf)    => "W"
  case Move(Goat)    => "G"
  case Move(Cabbage) => "C"
})

// Exiting paste mode, now interpreting.

defined trait Character
defined object Farmer
defined object Wolf
defined object Goat
defined object Cabbage
defined class Move
defined class Plan
defined trait Position
defined object West
defined object East
moveShow: cats.Show[Move] = cats.Show$$anon$2@6646f44c

makeNMoves 

Here’s making n moves

scala> val possibleMoves = List(Farmer, Wolf, Goat, Cabbage) map {Move(_)}
possibleMoves: List[Move] = List(Move(Farmer), Move(Wolf), Move(Goat), Move(Cabbage))

scala> :paste
// Entering paste mode (ctrl-D to finish)
def makeMove(ps: List[List[Move]]): List[List[Move]] =
  (ps |@| possibleMoves) map { (p, m) =>  List(m) <+> p }
def makeNMoves(n: Int): List[List[Move]] =
  n match {
    case 0 => Nil
    case 1 => makeMove(List(Nil))
    case n => makeMove(makeNMoves(n - 1))
  }

// Exiting paste mode, now interpreting.

makeMove: (ps: List[List[Move]])List[List[Move]]
makeNMoves: (n: Int)List[List[Move]]

We can test this as follows:

scala> makeNMoves(1)
res0: List[List[Move]] = List(List(Move(Farmer)), List(Move(Wolf)), List(Move(Goat)), List(Move(Cabbage)))

scala> makeNMoves(2)
res1: List[List[Move]] = List(List(Move(Farmer), Move(Farmer)), List(Move(Wolf), Move(Farmer)), List(Move(Goat), Move(Farmer)), List(Move(Cabbage), Move(Farmer)), List(Move(Farmer), Move(Wolf)), List(Move(Wolf), Move(Wolf)), List(Move(Goat), Move(Wolf)), List(Move(Cabbage), Move(Wolf)), List(Move(Farmer), Move(Goat)), List(Move(Wolf), Move(Goat)), List(Move(Goat), Move(Goat)), List(Move(Cabbage), Move(Goat)), List(Move(Farmer), Move(Cabbage)), List(Move(Wolf), Move(Cabbage)), List(Move(Goat), Move(Cabbage)), List(Move(Cabbage), Move(Cabbage)))

isSolution 

Let’s define our helper function isSolution :: Plan -> Bool. Basically, we want to check if the positions of all of the characters are East.

We can define filter using just what’s available in Alternative:

scala> :paste
// Entering paste mode (ctrl-D to finish)
def filterA[F[_]: Alternative, A](fa: F[A])(cond: A => Boolean): F[A] =
  {
    var acc = Alternative[F].empty[A]
    Alternative[F].map(fa) { x =>
      if (cond(x)) acc = Alternative[F].combineK(acc, Alternative[F].pure(x))
      else ()
    }
    acc
  }
def positionOf(p: List[Move], c: Character): Position =
  {
    def positionFromCount(n: Int): Position = {
      if (n % 2 == 0) West
      else East
    }
    c match {
      case Farmer => positionFromCount(p.size)
      case x      => positionFromCount(filterA(p)(_ == Move(c)).size)
    }
  }


// Exiting paste mode, now interpreting.

filterA: [F[_], A](fa: F[A])(cond: A => Boolean)(implicit evidence$1: cats.Alternative[F])F[A]
positionOf: (p: List[Move], c: Character)Position

scala> val p = List(Move(Goat), Move(Farmer), Move(Wolf), Move(Goat))
p: List[Move] = List(Move(Goat), Move(Farmer), Move(Wolf), Move(Goat))

scala> positionOf(p, Farmer)
res2: Position = West

scala> positionOf(p, Wolf)
res3: Position = East

Here’s how we can check all positions are East:

scala> :paste
// Entering paste mode (ctrl-D to finish)
def isSolution(p: List[Move]) =
  {
    val pos = (List(p) |@| possibleMoves) map { (p, m) => positionOf(p, m.x) }
    (filterA(pos)(_ == West)).isEmpty
  }

// Exiting paste mode, now interpreting.

isSolution: (p: List[Move])Boolean

makeMove 

What makes a move legal? Well, the farmer has to be on the same side as whatever is being moved.

scala> def moveLegal(p: List[Move], m: Move): Boolean =
         positionOf(p, Farmer) == positionOf(p, m.x)
moveLegal: (p: List[Move], m: Move)Boolean

scala> moveLegal(p, Move(Wolf))
res4: Boolean = false

The plan is safe if nothing can eat anything else. That means if the wolf and goat or goat and cabbage sit on the same bank, so too must the farmer.

scala> :paste
// Entering paste mode (ctrl-D to finish)
def safePlan(p: List[Move]): Boolean =
  {
    val posGoat = positionOf(p, Goat)
    val posFarmer = positionOf(p, Farmer)
    val safeGoat = posGoat != positionOf(p, Wolf)
    val safeCabbage = positionOf(p, Cabbage) != posGoat
    (posFarmer == posGoat) || (safeGoat && safeCabbage)
  }

// Exiting paste mode, now interpreting.

safePlan: (p: List[Move])Boolean

Using these functions we can now re-implement makeMove:

scala> :paste
// Entering paste mode (ctrl-D to finish)
def makeMove(ps: List[List[Move]]): List[List[Move]] =
  (ps |@| possibleMoves) map { (p, m) =>
  if (!moveLegal(p, m)) Nil
  else if (!safePlan(List(m) <+> p)) Nil
  else List(m) <+> p
}
def makeNMoves(n: Int): List[List[Move]] =
  n match {
    case 0 => Nil
    case 1 => makeMove(List(Nil))
    case n => makeMove(makeNMoves(n - 1))
  }
def findSolution(n: Int): Unit =
  filterA(makeNMoves(n))(isSolution) map { p =>
    println(p map {_.show})
  }

// Exiting paste mode, now interpreting.

makeMove: (ps: List[List[Move]])List[List[Move]]
makeNMoves: (n: Int)List[List[Move]]
findSolution: (n: Int)Unit

Let’s try solving the puzzle:

scala> findSolution(6)

scala> findSolution(7)
List(G, F, C, G, W, F, G)
List(G, F, W, G, C, F, G)

scala> findSolution(8)
List(G, F, C, G, W, F, G)
List(G, F, W, G, C, F, G)
List(G, F, C, G, W, F, G)
List(G, F, W, G, C, F, G)
List(G, F, C, G, W, F, G)
List(G, F, W, G, C, F, G)

It worked. That’s all for today.