Sketch of a generic formula tree optimizer. Idea is to use for Map/Reduce in summingbird where there are only binary (merge) and unary (map, reduce, etc...) operators.

gistfile1.scala

trait Family[F <: Family[F,V], V] { // might not need F-bound here, try to remove
  type Unary <: (V => V)
  type Binary <: ((V, V) => V)
}

sealed trait Formula[F <: Family[F,T], T] {
  def eval: T
}
/** eval could be made lazy, but pattern matching on it could be useful */
case class Res[F <: Family[F,T], T](eval: T) extends Formula[F, T]
case class Un[F <: Family[F,T], T](op: F#Unary, input0: Formula[F, T]) extends Formula[F, T] {
  def eval = op(input0.eval)
}
case class Bin[F <: Family[F,T], T](op: F#Binary,
  input0: Formula[F, T], input1: Formula[F, T]) extends Formula[F, T] {
  def eval = op(input0.eval, input1.eval)
}

trait Rule[F <: Family[F,T], T] {
  def apply(in: Formula[F, T]): Option[Formula[F, T]]
}

// Used to compare costs
trait Cost[F <: Family[F, T], T, C] {
  def ordering: Ordering[C]
  def cost(f: Formula[F, T]): C
}

/** Does not need to know about the details of Rules or Costs */
trait Optimizer[F <: Family[F, T], T, C] {
  def costModel: Cost[F, T, C]
  def rules: List[Rule[F, T]]

  def optimize(f: Formula[F, T]): Formula[F, T]
}

///////////////////////////

sealed trait BoolUn extends (Boolean => Boolean)
case object Not extends BoolUn {
  def apply(in: Boolean) = !in
}
sealed trait BoolBin extends ((Boolean, Boolean) => Boolean)
case object And extends BoolBin {
  def apply(in0: Boolean, in1: Boolean) = in0 && in1
}
case object Or extends BoolBin {
  def apply(in0: Boolean, in1: Boolean) = in0 || in1
}

object BooleanLogic {
  /** This seems like jank, but I can't get the compile happy without it */
  type Form = Formula[BooleanLogic, Boolean]
  def not(x: Form): Un[BooleanLogic, Boolean] =
    Un[BooleanLogic, Boolean](Not: BoolUn, x)
  def and(a: Form, b: Form): Bin[BooleanLogic, Boolean] =
    Bin[BooleanLogic, Boolean](And: BoolBin, a, b)
  def or(a: Form, b: Form): Bin[BooleanLogic, Boolean] =
    Bin[BooleanLogic, Boolean](Or: BoolBin, a, b)
}

class BooleanLogic extends Family[BooleanLogic, Boolean] {
  type Unary = BoolUn
  type Binary = BoolBin
}
object Distributive extends Rule[BooleanLogic, Boolean] {
  import BooleanLogic._
  def apply(form: Form) = form match {
    // a && (b || c) == (a && b) || (a && c)
    case Bin(And, a, Bin(Or, b, c)) => Some(or(and(a, b), and(a, c)))

    // a || (b && c) == (a || b) && (a || c)
    case Bin(Or, a, Bin(And, b, c)) => Some(and(or(a, b), or(a, c)))
    case _ => None
  }
}

object InvDistributive extends Rule[BooleanLogic, Boolean] {
  import BooleanLogic._
  def apply(form: Form) = form match {
    // (a || b) && (a || c) ==  a || (b && c)
    case Bin(And, Bin(Or, a1, b), Bin(Or, a2, c)) if(a1 == a2) =>
      Some(and(or(a1, b), or(a1, c)))

    // (a && b) || (a && c) = a && (b || c)
    case Bin(Or, Bin(And, a1, b), Bin(And, a2, c)) if(a1 == a2) =>
      Some(or(and(a1, b), and(a1, c)))

    case _ => None
  }
}


object BooleanCost extends Cost[BooleanLogic, Boolean, Int] {
  def ordering = Ordering[Int]
  def cost(f: Formula[BooleanLogic, Boolean]): Int = f match {
    case Bin(_, f1, f2) => 1 + cost(f1) + cost(f2)
    case Un(_, f1) => 1 + cost(f1)
    case Res(v) => 1
  }
}