これは、scala langWebサイトからPDFとして入手できるScalabyExampleの本でカバーされていると思います（第7章を参照）。私の提案は、ケースクラスを使用して式を表現し、パターンマッチングを使用して式を単純化することです。
まず、あらゆる種類の式を表すために使用される式の特性を定義しましょう。
scala> trait Expr { def simplify:Expr = this }
defined trait Expr
ここでは、Exprトレイトにsimplify、トレイトを拡張するオブジェクトを返すだけのデフォルトのメソッドを実装させました。それでは、いくつかの簡単な式を追加しましょう。
scala> case object True extends Expr
defined module True
scala> case object False extends Expr
defined module False
scala> case class Var(name:String) extends Expr { override def toString = name }
defined class Var
Trueそして、あなたの例でFalseはとを表します。まだ真理値を持たない変数を表すために使用されます。たとえば、例ではx、y、a、bです。Varはまた、印刷を少しきれいにする方法を上書きします:)1nilVartoString
さて、および/またはで少しトリッキーな状況になります。これらを次のように定義しましょう：
scala> case class And(a:Expr, b:Expr) extends Expr {
| override def simplify = (a.simplify, b.simplify) match {
| case (True,x) => x
| case (x,True) => x
| case (False,x) => False
| case (x,False) => False
| case (x,y) => And(x,y)
| }
| }
defined class And
scala> case class Or(a:Expr, b:Expr) extends Expr {
| override def simplify = (a.simplify, b.simplify) match {
| case (True,x) => True
| case (x,True) => True
| case (False,x) => x
| case (x,False) => x
| case (x,y) => Or(x,y)
| }
| }
defined class Or
And両方とも、トレイトのメソッドをOrオーバーライドし、それら自体とそのサブエクスプレッションの簡略化されたバージョンを返します。これで、これらを使用して、より単純なTrue、False、およびVar式とともに式を作成できます。simplifyExpr
scala> val X = Var("X"); val Y = Var("Y"); val A = Var("A"); val B = Var("B")
X: Var = X
Y: Var = Y
A: Var = A
B: Var = B
scala> And(X, True).simplify
res10: Expr = X
scala> And(X, And(Y, False)).simplify
res11: Expr = False
scala> And(X, Or(Y, False)).simplify
res12: Expr = And(X,Y)
scala> Or(True, And(X, Or(Y, False))).simplify
res13: Expr = True
最後に、notの式を追加します。
scala> case class Not(a:Expr) extends Expr {
| override def simplify = a.simplify match {
| case True => False
| case False => True
| case And(x,y) => Or(Not(x),Not(y))
| case Or(x,y) => And(Not(x),Not(y))
| case Not(x) => x
| case x => Not(x)
| }
| }
defined class Not
これで、例の式を表すことができます。ただし、一部の式では、このNotcaseクラスは完全な単純化を行いません。
scala> Not(Or(Not(X),Y)).simplify
res41: Expr = And(Not(Not(X)),Not(Y))
Notしたがって、式を単純化できなくなるまで式を単純化しようとする再帰関数を定義できます。
scala> case class Not(a:Expr) extends Expr {
| override def simplify = recursiveSimplify(a, a)
| private def recursiveSimplify(curExpr:Expr, lastExpr:Expr):Expr = if(curExpr != lastExpr) {
| val newExpr = curExpr.simplify match {
| case True => False
| case False => True
| case Var(x) => Not(Var(x))
| case Not(x) => x
| case And(x,y) => Or(Not(x), Not(y))
| case Or(x,y) => And(Not(x), Not(y))
| }
| recursiveSimplify(newExpr, curExpr)
| } else {
| lastExpr
| }
| }
defined class Not
これで、以前の式は次のように簡略化されます。
scala> Not(Or(Not(X),Y)).simplify
res42: Expr = Or(Not(X),Y)