Бесконечный цикл scala-код

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

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

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

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

Заранее благодарен!

источник

2012-02-25 Sander

Проблема заключается в том, что вы пытаетесь сделать две вещи за один шаг, которые должны выполняться последовательно, применяя закон Де Моргана (и устраняя двойное отрицание) и рекурсивное упрощение любых детей. Вот почему просто отбрасывание 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 
}

источник

2012-02-25 23:11:47

Я понимаю, что вы имеете в виду. Хотя мое назначение говорит мне явно использовать объект-компаньон.' Prop.simplify (Prop): Prop, который возвращает упрощенное и эквивалентное предложение, неоднократно применяя закон Моргана и двойное отрицание к эллимизации аргумента предложения. Полученное предложение должно соответствовать требованиям, изложенным ниже. «Также ваше предложение не полностью соответствует мои лекторы отвечают (у нас есть система для выполнения нашей работы против теста). Смотрите: http://pastebin.com/WDuQKreD (также для полной трески e в данный момент) Спасибо в любом случае! – Sander

@Sander: вам просто нужно добавить случаи для «упрощения» для других операций (также, извините, я не понял, что это домашнее задание - я бы не был так прямо в своем ответе). –

@Sander: Кроме того, как наследование класса case, так и класс case с пустым конструктором являются плохими. 'trait Prop; case object True расширяет Prop' лучше. –

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

simplify(prop)

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

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

Однако исправление (на основе кода) прост:

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

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

case _ => prop

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

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

источник

2012-02-25 21:59:33

Спасибо за ваш ответ. Я пытался это сделать. (Извините, нажал ввод и отправил, не желая). Но в некоторых случаях упрощение приводит к тому, что строка содержит новый Not (Not (a)), поэтому повторное упрощение приведет к их устранению. Но я не могу заставить его запускать его снова, когда они кажутся новым совпадением в любом из предыдущих случаев ..: \ – Sander

@Sander: можете ли вы показать нам ввод, который не упрощает 'Not (Not (a)) '? Это можно устранить, вызвав 'simplify()' на отдельных терминах типа e.g: упростить 'And (Not (Not (a)), b)' вы должны возвращать 'И (упростить (Not (Not (a)), упростить (b))' (шаблон упрощения: 'И (a , b) => И (упростить (a), упростить (b)) '. –

@Thomasz' Not (And (Not (a), Not (b))) 'Это сначала упростит до или Или (Not (Not (a)), Not (Not (b))), насколько я могу видеть. Код должен повторно запускаться, чтобы исключить вновь созданные Not (Not (a)) и Not (Not (b)). – Sander

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

источник

2012-02-25 22:06:44 mmmbell

Бесконечный цикл scala-код

ответ

Смежные вопросы