Alternative 

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

@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 で実装してみよう。

Wolf, Goat, Cabbage: Solving simple logic problems in #haskell using the List MonadPlus :) http://t.co/YkKi6EQdDy

— Justin Le (@mstk) December 26, 2013

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

import cats._, cats.syntax.all._

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 lazy val moveShow = Show.show[Move](_ match {
  case Move(Farmer)  => "F"
  case Move(Wolf)    => "W"
  case Move(Goat)    => "G"
  case Move(Cabbage) => "C"
})

makeNMoves0 

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

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

def makeMove0(ps: List[List[Move]]): List[List[Move]] =
  (ps , possibleMoves) mapN { (p, m) =>  List(m) <+> p }

def makeNMoves0(n: Int): List[List[Move]] =
  n match {
    case 0 => Nil
    case 1 => makeMove0(List(Nil))
    case n => makeMove0(makeNMoves0(n - 1))
  }

テストしてみる:

makeNMoves0(1)
// res0: List[List[Move]] = List(
//   List(Move(x = Farmer)),
//   List(Move(x = Wolf)),
//   List(Move(x = Goat)),
//   List(Move(x = Cabbage))
// )

makeNMoves0(2)
// res1: List[List[Move]] = List(
//   List(Move(x = Farmer), Move(x = Farmer)),
//   List(Move(x = Wolf), Move(x = Farmer)),
//   List(Move(x = Goat), Move(x = Farmer)),
//   List(Move(x = Cabbage), Move(x = Farmer)),
//   List(Move(x = Farmer), Move(x = Wolf)),
//   List(Move(x = Wolf), Move(x = Wolf)),
//   List(Move(x = Goat), Move(x = Wolf)),
//   List(Move(x = Cabbage), Move(x = Wolf)),
//   List(Move(x = Farmer), Move(x = Goat)),
//   List(Move(x = Wolf), Move(x = Goat)),
//   List(Move(x = Goat), Move(x = Goat)),
//   List(Move(x = Cabbage), Move(x = Goat)),
//   List(Move(x = Farmer), Move(x = Cabbage)),
//   List(Move(x = Wolf), Move(x = Cabbage)),
//   List(Move(x = Goat), Move(x = Cabbage)),
//   List(Move(x = Cabbage), Move(x = Cabbage))
// )

isSolution 

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

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

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

val p = List(Move(Goat), Move(Farmer), Move(Wolf), Move(Goat))
// p: List[Move] = List(
//   Move(x = Goat),
//   Move(x = Farmer),
//   Move(x = Wolf),
//   Move(x = Goat)
// )

positionOf(p, Farmer)
// res2: Position = West

positionOf(p, Wolf)
// res3: Position = East

全ての位置が East であるかは以下のようにチェックできる:

def isSolution(p: List[Move]) =
  {
    val pos = (List(p), possibleMoves) mapN { (p, m) => positionOf(p, m.x) }
    (filterA(pos)(_ == West)).isEmpty
  }

makeMove 

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

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

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

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

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

これらの関数を使って makeMove を再実装できる:

def makeMove(ps: List[List[Move]]): List[List[Move]] =
  (ps, possibleMoves) mapN { (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})
  }

パズルを解いてみる:

findSolution(6)

findSolution(7)
// List(G, F, C, G, W, F, G)
// List(G, F, W, G, C, F, G)

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)

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