Alternative 

Alternative という ApplicativeMonoidK を組み合わせた型クラスがある:

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

Alternative そのものは新しいメソッドや演算子を導入しない。

これは Monad 上に filter などを追加する MonadPlus を弱くした (なのでかっこいい) Applicative 版だと考えることができる。 Applicative スタイルについては3日目を参照。

Alternative 則 

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))

}

最後の法則に関しては、それが不必要では無いかという未回答なままの質問が吉田さんから出ている。

オオカミ、ヤギ、キャベツ 

Justin Le (@mstk) さんが 2013年に書いた 「オオカミ、ヤギ、キャベツ: List MonadPlus とロジックパズル」Alternative で実装してみよう。

ある農家の人が持ち物のオオカミ、ヤギ、キャベツを連れて川を渡ろうとしている。ところが、ボートには自分以外もう一つのものしか運ぶことができない。オオカミとヤギを放ったらかしにすると、ヤギが食べられてしまう。ヤギとキャベツを放ったらかしにすると、キャベツが食べられてしまう。損害が無いように持ち物を川の向こうまで渡らせるにはどうすればいいだろうか?

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@4ccb94bf

makeNMoves 

n 回の動きはこのように表現できる。

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]]

テストしてみる:

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 

ヘルパー関数の isSolution :: Plan -> Bool を定義してみよう。 基本的にh,全てのキャラクターの位置が East であることをチェックする。

Alternative にあるものだけで filter を定義できる:

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

全ての位置が 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 

合法な動きとはどういうことだろう? とりあえず、農家の人が川の同じ岸にいる必要がある。

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

誰も何も食べなければ、計画は安全だと言える。つまり、オオカミとヤギ、もしくはヤギとキャベツが同じ岸にいる場合は農家の人も一緒にいる必要がある。

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

これらの関数を使って 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

パズルを解いてみる:

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)

うまくいった。今日はここまで。