Extending Scala pattern matching in subclass while maintaining complexity

Question

I have an Scala question. Imagine you're building code to handle different operations, i.e.

operation match {
   case A => doA()
   case B => doB()
   case _ => throw new Exception("Unknown op: " + operation)
}

Now, imagine that later on you wanna build a new version and you want to extend that pattern matching for operation C. How can you do it in such way that operation resolution is still O(1)?

I mean, I could modify the code above to do:

   case _ => handleUnknownOperation(operation)

And a subclass could implement handleUnknownOperation to do:

operation match {
   case C => doC()
}

But this is sucky cos it means that C operation requires O(2).

Any other ideas, or best practices for extending this kind of pattern matching structures?

Cheers, Galder

Answer 1

To answer the original question, pattern matching is effectively translated into a series of if/else statements, just a series of tests. The case _ at the end is just a fallthrough (without an associated test). So there is very little difference between having A, B and C in a single match and A and B in a match and then delegating to another match which matches C. Using the following as an example:

class T

case class A(v: Int) extends T
case class B(v: Int) extends T
case class C(v: Int) extends T

class Foo {
  def getOperation(t: T): Unit = {
    t match {
      case A(2) => println("A")
      case B(i) => println("B")
      case _ => unknownOperation(t)
    }
  }

  def unknownOperation(t: T): Unit = println("unknown operation t=" + t)
}

class Bar extends Foo {
  override def unknownOperation(t: T): Unit = t match {
    case C(i) => println("C")
    case _ => println("unknown operation t=" + t)
  }
}

Using jad to decompile Foo.class, we get:

public void getOperation(T t) {
label0:
    {
        T t1 = t;
        if(t1 instanceof A)
        {
            if(((A)t1).v() == 2)
            {
                Predef$.MODULE$.println("A");
                break label0;
            }
        } else
        if(t1 instanceof B)
        {
            Predef$.MODULE$.println("B");
            break label0;
        }
        unknownOperation(t);
    }
}

So, I would say that you shouldn't worry about performance[*].

However, from a design point of view I would probably switch things around a bit and either use the Command pattern as Frank suggests, or instead of overriding unknownOperation in the subclass, you could override getOperation, which does the match against C and then delegates to super.getOperation(), which seems neater to me.

class Bar extends Foo {
  override def getOperation(t: T): Unit = t match {
    case C(i) => println("C")
    case _ => super.getOperation(t)
  }
}

[*] The caveat to this would be complexity. There is an issue in pre-2.10 versions of Scala in which the pattern matcher generates .class files which are too complex (nested extractors generate exponential-space bytecode), so if you're using a match which is very complex, this can cause problems. This is fixed in 2.10 with the virtual pattern matcher. If you're having this problem, then one of the workarounds for this bug is to split your pattern matches into different methods/classes.

Answer 2

re: a handleUnknownOperation method, that's not a terribly clean OO design. For example, it become's a bit odd when you want to handle a D operation if a v3 subclass. Instead, just create a handle method that subclasses can override:

class BaseProtocol {
  def handle(operation: Operation) = operation match {
    case A => doA()
    case B => doB()
    case _ => throw new Exception("Unknown op: " + operation)
  }
}

class DerivedProtocol extends BaseProtocol {
  override def handle(operation: Operation) = operation match {
    case C => doC()
    case _ => super.handle(operation)
  }
}

re: efficiency, you are probably prematurely optimizing, but I won't let that stop me :-)

Are all of your operations objects? If so, you can replace the match statements with a Map.

class BaseProtocol {
  def handlers = Map(A -> doA _, B -> doB _)

  def handle(operation: Operation) =
    handlers.get(operation)
      .getOrElse(throw new Exception("Unknown op: " + operation))
      .apply()
}

class DerivedProtocol extends BaseProtocol {
  override def handlers = super.handlers + (C -> doC _)
}