CODEWITHSUNDEEP
scalaoopinheritanceabstract-class
dividebyzero
dividebyzero

Reputation: 2239

How to design abstract classes if methods don't have the exact same signature?

This is a "real life" OO design question. I am working with Scala, and interested in specific Scala solutions, but I'm definitely open to hear generic thoughts.

I am implementing a branch-and-bound combinatorial optimization program. The algorithm itself is pretty easy to implement. For each different problem we just need to implement a class that contains information about what are the allowed neighbor states for the search, how to calculate the cost, and then potentially what is the lower bound, etc...

I also want to be able to experiment with different data structures. For instance, one way to store a logic formula is using a simple list of lists of integers. This represents a set of clauses, each integer a literal. We can have a much better performance though if we do something like a "two-literal watch list", and store some extra information about the formula in general.

That all would mean something like this

object BnBSolver[S<:BnBState]{
  def solve(states: Seq[S], best_state:Option[S]): Option[S] = if (states.isEmpty) best_state else
     val next_state = states.head
     /* compare to best state, etc... */
     val new_states = new_branches ++ states.tail
     solve(new_states, new_best_state)
}

class BnBState[F<:Formula](clauses:F, assigned_variables) {
  def cost: Int

  def branches: Seq[BnBState] = {
    val ll = clauses.pick_variable
    List(
      BnBState(clauses.assign(ll), ll :: assigned_variables), 
      BnBState(clauses.assign(-ll), -ll :: assigned_variables)
    )
  }
}

case class Formula[F<:Formula[F]](clauses:List[List[Int]]) {
    def assign(ll: Int) :F = 
       Formula(clauses.filterNot(_ contains ll)
                      .map(_.filterNot(_==-ll))))

}

Hopefully this is not too crazy, wrong or confusing. The whole issue here is that this assign method from a formula would usually take just the current literal that is going to be assigned. In the case of two-literal watch lists, though, you are doing some lazy thing that requires you to know later what literals have been previously assigned.

One way to fix this is you just keep this list of previously assigned literals in the data structure, maybe as a private thing. Make it a self-standing lazy data structure. But this list of the previous assignments is actually something that may be naturally available by whoever is using the Formula class. So it makes sense to allow whoever is using it to just provide the list every time you assign, if necessary.

The problem here is that we cannot now have an abstract Formula class that just declares a assign(ll:Int):Formula. In the normal case this is OK, but if this is a two-literal watch list Formula, it is actually an assign(literal: Int, previous_assignments: Seq[Int]).

From the point of view of the classes using it, it is kind of OK. But then how do we write generic code that can take all these different versions of Formula? Because of the drastic signature change, it cannot simply be an abstract method. We could maybe force the user to always provide the full assigned variables, but then this is a kind of a lie too. What to do?

The idea is the watch list class just becomes a kind of regular assign(Int) class if I write down some kind of adapter method that knows where to take the previous assignments from... I am thinking maybe with implicit we can cook something up.

Upvotes: 1

Views: 77

Answers (1)

Joe K
Joe K

Reputation: 18434

I'll try to make my answer a bit general, since I'm not convinced I'm completely following what you are trying to do. Anyway...

Generally, the first thought should be to accept a common super-class as a parameter. Obviously that won't work with Int and Seq[Int].

You could just have two methods; have one call the other. For instance just wrap an Int into a Seq[Int] with one element and pass that to the other method.

You can also wrap the parameter in some custom class, e.g.

class Assignment {
  ...
}
def int2Assignment(n: Int): Assignment = ...
def seq2Assignment(s: Seq[Int]): Assignment = ...
case class Formula[F<:Formula[F]](clauses:List[List[Int]]) {
    def assign(ll: Assignment) :F = ...
}

And of course you would have the option to make those conversion methods implicit so that callers just have to import them, not call them explicitly.

Lastly, you could do this with a typeclass:

trait Assigner[A] {
  ...
}
implicit val intAssigner = new Assigner[Int] {
  ...
}
implicit val seqAssigner = new Assigner[Seq[Int]] {
  ...
}
case class Formula[F<:Formula[F]](clauses:List[List[Int]]) {
    def assign[A : Assigner](ll: A) :F = ...
}

You could also make that type parameter at the class level:

case class Formula[A:Assigner,F<:Formula[A,F]](clauses:List[List[Int]]) {
    def assign(ll: A) :F = ...
}

Which one of these paths is best is up to preference and how it might fit in with the rest of the code.

Upvotes: 4

Related Questions