Geek Answers Handbook

Infinite loop scala code

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

I am sure that I have an infinite loop caused by my default case. In all cases, I use recursion. It should be, but only if Prop can be simplified. As soon as Prop cannot be simplified, it should return all this.

I do not see how I can verify further simplification. (I am not allowed to use other libraries, as suggested in the freenodes # scala channel).

Can someone explain if this is a “case” causing a loop, and how to solve it? How can I check for possible simplification without creating a loop?

Thanks in advance!

+5
source share
3 answers

, , , ( ) . 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
}
+6

, , 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. , .

+9

Yes, the default case causes a loop. if (simplify(prop) == prop) propis a problematic line. You do not need to check if it can be simplified, because when you are in the default case, all possible simplifications are checked.

+2
source

More articles:


All Articles