LogicLike version of: http://ambassadortothecomputers.blogspot.com/2011/04/logic-programming-in-scala-part-1.html

logic.scala

trait LogicLike[A, This[A] <: LogicLike[A, This]] {
  def or(t: => This[A]): This[A]
  def map[B](f: A => B): This[B]
  def flatMap[B](f: A => This[B]): This[B]
  def filter(p: A => Boolean): This[A]
  def split: Option[(A, This[A])]
  def |(t: => This[A]): This[A] = or(t)

  def run(n: Int): List[A] =
    if (n <= 0) Nil else
      split match {
        case None => Nil
        case Some((a, t)) => a :: t.run(n - 1)
      }
}

/**
 * This really just knows how to "lift" values into the logic monad.
 */
trait Logic {
  type This[A] <: LogicLike[A, This]

  def fail[A]: This[A]
  def unit[A](a: A): This[A]
  def or[A](as: List[A]): This[A] =
    as.foldRight(fail[A])((a, t) => unit(a).or(t))
}

class ListLogic[A](private[ListLogic] val l: List[A]) extends LogicLike[A, ListLogic]
{
  def or(t: => ListLogic[A]): ListLogic[A] = new ListLogic(l ::: t.l)
  def map[B](f: A => B): ListLogic[B] = new ListLogic(l.map(f))
  def flatMap[B](f: A => ListLogic[B]): ListLogic[B] =
    new ListLogic(l.flatMap(f(_).l))
  def filter(p: A => Boolean): ListLogic[A] = new ListLogic(l.filter(p))
  def split: Option[(A, ListLogic[A])] =
    l match {
      case Nil => None
      case h :: t => Some(h, new ListLogic(t))
    }
}

object ListLogic extends Logic {
  type This[A] = ListLogic[A]

  def fail[A] = new ListLogic(Nil)
  def unit[A](a: A) = new ListLogic(a :: Nil)
}

class Bridge(logic: Logic) {
  import logic._

  object Person extends Enumeration {
    type Person = Value
    val Alice, Bob, Candace, Dave = Value
    val all = List(Alice, Bob, Candace, Dave) // values is broken
  }
  import Person._

  val times = Map(Alice -> 5, Bob -> 10, Candace -> 20, Dave -> 25)

  case class State(left: List[Person],
                   lightOnLeft: Boolean,
                   timeRemaining: Int)

  private def chooseTwo(list: List[Person]): This[(Person,Person)] =
    for { p1 <- logic.or(list); p2 <- logic.or(list); if p1 < p2 }
    yield (p1, p2)

  private def next(state: State): This[State] = {
    if (state.lightOnLeft) {
      for {
        (p1, p2) <- chooseTwo(state.left)
        timeRemaining =
          state.timeRemaining - math.max(times(p1), times(p2))
        if timeRemaining >= 0
      } yield {
        val left =
          state.left.filterNot { p => p == p1 || p == p2 }
        State(left, false, timeRemaining)
      }
    } else {
      val right = Person.all.filterNot(state.left.contains)
      for {
        p <- logic.or(right)
        timeRemaining = state.timeRemaining - times(p)
        if timeRemaining >= 0
      } yield State(p :: state.left, true, timeRemaining)
    }
  }

  private def tree(path: List[State]): This[List[State]] =
    logic.unit(path) |
      (for {
         state <- next(path.head)
         path <- tree(state :: path)
       } yield path)

  def search(n: Int): List[List[State]] = {
    val start = List(State(Person.all, true, 60))
    val t =
      for { path <- tree(start); if path.head.left == Nil }
      yield path
    t.run(n)
  }
}