Скала код с бесконечным циклом - PullRequest
Новая
       53

Скала код с бесконечным циклом

5 голосов
/ 26 февраля 2012 
object Prop {
  def simplify(prop : Prop) : Prop = {
    prop match {
      case Not(Or(a,b)) => simplify(And(Not(a),Not(b)))
      case Not(And(a,b)) => simplify(Or(Not(a),Not(b)))
      case Not(Not(a)) => simplify(a)
      case _ => {
        if (simplify(prop) == prop) prop
        else prop
      }
    }
  }
}

Я почти уверен, что у меня бесконечный цикл, вызванный моим делом по умолчанию. Я использую рекурсию во всех случаях. Что должно быть, но, только если Опора может быть упрощена. Как только Опора не может быть упрощена, она должна вернуть все это.

Я не вижу, как я могу проверить дальнейшее упрощение. (Мне не разрешено использовать другие библиотеки, как предложено в канале freenodes #scala).

Может кто-нибудь объяснить, является ли это «случаем _», вызывающим цикл, и как его решить? Как я могу проверить на возможное упрощение без создания цикла?

Заранее спасибо!

Ответы [ 3 ]

9 голосов
/ 26 февраля 2012

Довольно очевидно, что происходит, и вы правы со значением по умолчанию case. Если ваш ввод prop не соответствует ни одному из случаев, которые вы вызываете: 

simplify(prop)

с тем же аргументом. Поскольку ранее это вызывало рекурсивный вызов simplify(), и вы вызываете свою функцию с тем же вводом, он снова вводит simplify(). Так что это не бесконечный цикл, а рекурсивный вызов, который никогда не завершается: 

...simplify(simplify(simplify(simplify(simplify(simplify(simplify(prop)))))))

Однако исправить (в зависимости от вашего кода) просто: 

if (simplify(prop) == prop) prop
    else prop

просто замените его на ... 

 case _ => prop

Обе ветви возвращают одно и то же значение. Это на самом деле правильно, если вы думаете, если на какое-то время. У вас есть набор оптимизаций. Если ни одно из них не соответствует вашим выражениям, это означает, что его больше нельзя упростить. Следовательно, вы возвращаете его как есть.

Кстати, похоже, вы делаете упрощение логических выражений с помощью классов case. Вас может заинтересовать моя статья , где я делаю то же самое, но с арифметическими выражениями.

6 голосов
/ 26 февраля 2012

Проблема в том, что вы пытаетесь сделать две вещи в одном шаге, которые должны происходить последовательно - применить закон Де Моргана (и устранить двойное отрицание) и рекурсивно упростить всех детей.Вот почему просто вставить case And(a, b) => And(simplify(a), simplify(b)) в match не получится.

Попробуйте выполнить следующее: 

val deMorganAndDoubleNegation: Prop => Prop = {
  case Not(Or(a, b)) => And(Not(a), Not(b))
  case Not(And(a, b)) => Or(Not(a), Not(b))
  case Not(Not(a)) => a
  case a => a
}

val simplify: Prop => Prop = deMorganAndDoubleNegation andThen {
  case And(a, b) => And(simplify(a), simplify(b))
  case Or(a, b) => Or(simplify(a), simplify(b))
  case Not(a) => Not(simplify(a))
  case a => a
}
2 голосов
/ 26 февраля 2012

Да, случай по умолчанию вызывает цикл.if (simplify(prop) == prop) prop это проблемная строка.Вам не нужно проверять, можно ли его еще больше упростить, потому что в случае по умолчанию пробуются все возможные упрощения.

...