无限循环scala代码

Question

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.一旦道具不能简化,就应该归还整个东西.

我不知道如何测试任何进一步的简化.(我不允许使用其他库,如freenodes #scala频道所示).

有人可以解释它是否是导致循环的"case _",以及如何解决它？如何在不进行循环的情况下测试可能的简化？

提前致谢!

Answer 1

很明显会发生什么,你是默认的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类进行布尔表达式简化.您可能会对我的文章感兴趣,但我会使用算术表达式.

Answer 2

问题是你试图在一个步骤中做两件事,需要顺序发生 - 应用De Morgan定律(并消除双重否定)并递归地简化任何孩子.这就是为什么只是放弃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
}