Optimizing DNF converter

DNF.scala

import scala.reflect.ClassTag

trait Expr

case class Not(expr: Expr) extends Expr {
  override def toString = s"!$expr"
}

case class Value[T](t: T) extends Expr {
  override def toString = s"$t"
}

case object True extends Expr {
  override def toString = "T"
}

case object False extends Expr {
  override def toString = "F"
}


trait Aggregate extends Expr {
  def exprs: Set[Expr]
}

case class Or(e: Traversable[Expr]) extends Aggregate {
  override val exprs = e.toSet

  override def toString = e.mkString("|( ", " | ", " )")
}

object Or {
  def apply(exprs: Expr*): Or = new Or(exprs)
}

case class And(e: Traversable[Expr]) extends Aggregate {
  override val exprs = e.toSet

  override def toString = exprs.mkString("&( ", " & ", " )")
}

object And {
  def apply(exprs: Expr*): And = new And(exprs)
}


object DNF {
  def toDNF(e: Expr): Expr = {
    e match {
      case v@Not(_: Aggregate) =>
        toDNF(distributionLaw(v))

      case v: Or =>
        doOr(v.exprs.map(toDNF))

      case v: And =>
        val conjunction = doAnd(v.exprs.map(toDNF))

        conjunction match {
          case a: And =>
            val (disjunctions, conjunctions) = a.exprs.foldLeft((List.empty[Or], Set.empty[Expr])) {
              case (acc, c: Or) => (acc._1 :+ c, acc._2)
              case (acc, c) => (acc._1, acc._2 + c)
            }

            disjunctions match {
              case Nil =>
                conjunction
              case head :: tail =>
                toDNF(deMorganLaw(head, conjunctions ++ tail))
            }

          case o => o
        }

      case v =>
        v
    }
  }

  @inline private def deMorganLaw(disjunction: Or, conjunctions: Set[Expr]): Or = {
    new Or(disjunction.exprs.map(d => doAnd(conjunctions + d)))
  }

  @inline private def distributionLaw(v: Not): Expr = {
    v.expr match {
      case se: Value[_] => v
      case se: Not => se.expr
      case se: Or => doAnd(se.exprs.map(Not))
      case se: And => doOr(se.exprs.map(Not))
    }
  }

  @inline private def doAnd(exprs: Set[Expr]) = {
    val withoutTrue = exprs.filterNot(_ == True)
    doAgg[And](withoutTrue, v => new And(v)) match {
      case v: And if containsPair(v) => False
      case v => v
    }
  }

  @inline private def doOr(exprs: Set[Expr]): Expr = {
    val withoutFalse = exprs.filterNot(_ == False)
    doAgg[Or](withoutFalse, Or.apply) match {
      case v: Or if containsPair(v) => True
      case v => v
    }
  }

  @inline private def containsPair(a: Aggregate): Boolean = {
    a.exprs.exists(e => a.exprs.contains(Not(e)))
  }

  @inline private def doAgg[T <: Aggregate : ClassTag](exprs: Set[Expr], c: Traversable[Expr] => T): Expr = {
    exprs.flatMap {
      case a: T => a.exprs
      case v => Set(v)
    } match {
      case e if e.size == 1 => e.head
      case e => c(e)
    }
  }
}

DNF.toDNF(And(Value(1), Not(Value(1))))
DNF.toDNF(Or(Value(1), Not(Value(1))))
DNF.toDNF(And(Value(5), Value(6)))
DNF.toDNF(Or(Value(5), Value(6)))
DNF.toDNF(Not(And(Value(5), Value(6))))
DNF.toDNF(Not(Or(Value(5), Value(6))))
DNF.toDNF(And(Value(1), Or(Value(5), Value(6))))
DNF.toDNF(And(
  Value("x")
  , Value("y")
  , Or(
    Value("w")
    , Not(
      Value("v")
    )
  )
  , Not(And(Value("a"), Value("b")))
  , Not(Or(Value("x1"), Value("y1")))
)
)