fp_december2014.scala

import scalaz.NonEmptyList
import scalaz.syntax.monad._
import scalaz.syntax.equal._
import scalaz.syntax.foldable._
import scalaz.std.option._
import scalaz.std.list._
import scalaz.std.list.listSyntax._
import scalaz.std.anyVal._
import scalaz.std.string._
import scalaz.effect.IO
import scalaz.effect.IO._

object Main extends App {
  
  type Question = (String, List[String])
  
  val inputMatrix: List[Question] = List(
      ("Цвет лемпелей",            List("Жёлтый",  "Жёлтый",    "Жёлтый",    "Белый", "Белый")),
      ("Наличие бомбурий",         List("Да",      "Да",        "Нет",       "Да",    "Нет")),
      ("Количество клептиконов",   List("1",       "1",         "0",         "3",     "5")),
      ("Цвет велория",             List("Красный", "Оранжевый", "Оранжевый", "—",     "Синий")),
      ("Наличие пумпеля",          List("Нет",     "Да",        "Да",        "—",     "—")),
      ("Величина пумпеля",         List("—",       "Большой",   "Маленький", "—",     "—")),
      ("Возможность крокотания",   List("Нет",     "Нет",       "—",         "Да",    "Нет")),
      ("Возможность бульботания",  List("Нет",     "Да",        "—",         "Да",    "Нет")),
      ("Наличие дуков и труков",   List("—",       "—",         "—",         "—",     "Да")),
      ("Наличие пильских трапков", List("Да",      "Да",        "Да",        "Да",    "Да")))
      
  val answers = NonEmptyList(
      "Аурата сетуньская",
      "Десятилиньята лепая",
      "Семипунктата Коха",
      "Популий грыжомельский",
      "Гортикола филоперьевая")
      
  def newQuestions(questions: List[Question]): List[Question] = questions
    .filter{ case (_, replies) => replies.toSet.size ≠ 1 } // Убрать вопросы, в которых все ответы одинаковые
    .sortBy{ case (_, replies) => replies.count(_ === "—") } // В первую очередь задать вопросы, в которых нету "—"
  
  // Один вопрос. Возвращает новый список вопросов с новыми ответами.
  def step(questions: List[Question], answers: NonEmptyList[String], reply: String): (List[Question], NonEmptyList[String]) = {
    questions match {
      case Nil => (nil, answers)
      
      case (question, replies) :: otherQuestions => {
        if (reply === "—") {
          (newQuestions(otherQuestions), answers)
        } else replies.count(_ === reply) match {
          case 0 => ???
          
          case 1 => (nil, NonEmptyList(answers.index(replies.indexOf(reply)).get))
          
          case _ => {
            val indices: List[Int] = for { (r, index) <- (replies zip Stream.from(0)) if (r === reply) } yield index
            
            // Уменьшаем множество ответов
            val reducedAnswers: NonEmptyList[String] = (for { index <- indices } yield answers.index(index).get).toNel.get
            
            // Уменьшаем множество признаков
            val reducedQuestions: List[Question] = for {
              (question, replies) <- otherQuestions
            } yield (question, (for { index <- indices } yield replies.index(index).get))
            
            (newQuestions(reducedQuestions), reducedAnswers)
          }
        }
      } 
    }
  }

  def io(questions: List[Question], answers: NonEmptyList[String]): IO[Unit] = {
    answers.size match {
      case 1 => putStrLn("Ответ: " + answers.head)
      
      case _ => questions match {
        case Nil => putStrLn("Вопросы кончились. Возможные ответы: " + answers.toList.mkString(", "))
          
        case (question, replies) :: _ => {
          putStrLn(s"$question (Введите один из ответов: ${replies.toSet.mkString(", ")}):") >>
          readLn >>= (reply => {
            val (newQuestions, newAnswers) = step(questions, answers, reply)
            io(newQuestions, newAnswers)
          })
        }
      }
    }
  }
  
  io(newQuestions(inputMatrix), answers).unsafePerformIO()
}

Эх, не смог в поучаствовать в этот раз.
Все-таки Scalaz интересная штука, тебе как? Перфоманс не сильно страдает?

Scalaz - интересно, но не более того. Ну т.е. можно конечно в реальных приложениях использовать некоторые фишечки типа NonEmptyList или Scalaz.unfold(). Но по полной вряд ли получится, т.к. весь стек от самого низа до верха должен быть реализован с помощью Scalaz, но библиотек, написанных на Scalaz (веб-фреймворки, GUI-библиотеки), практически нету. По той же причине не взлетит и Frege. А вот в Haskell такой проблемы нету. Там монады включены в стандартную библиотеку, и поэтому повсеместно могут использоваться.
Про производительность ничего не могу сказать, но скорее всего она стремная.