scala - 无限循环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 可以简化。一旦 Prop 不能被简化，它应该返回整个事情。

我不知道如何测试任何进一步的简化。 (我不允许使用其他库，正如 freenodes #scala channel 中所建议的那样)。

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

提前致谢!

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

两个分支都返回相同的值。如果您考虑一下，这实际上是正确的。您有一组优化。如果它们都与您的表达式不匹配，则意味着它不能再被简化。因此，您将按原样返回。

顺便说一句，您似乎正在使用案例类进行 bool 表达式简化。您可能对我的 article 感兴趣在那里我做同样的事情，但使用算术表达式。