costly computation occuring in both isDefined and Apply of a PartialFunction

Question

It is quite possible that to know whether a function is defined at some point, a significant part of computing its value has to be done. In a PartialFunction, when implementing isDefined and apply, both methods will have to do that. What to do is this common job is costly?

There is the possibility of caching its result, hoping that apply will be called after isDefined. Definitely ugly.

I often wish that PartialFunction[A,B] would be Function[A, Option[B]], which is clearly isomorphic. Or maybe, there could be another method in PartialFunction, say applyOption(a: A): Option[B]. With some mixins, implementors would have a choice of implementing either isDefined and apply or applyOption. Or all of them to be on the safe side, performance wise. Clients which test isDefined just before calling apply would be encouraged to use applyOption instead.

However, this is not so. Some major methods in the library, among them collect in collections require a PartialFunction. Is there a clean (or not so clean) way to avoid paying for computations repeated between isDefined and apply?

Also, is the applyOption(a: A): Option[B] method reasonable? Does it sound feasible to add it in a future version? Would it be worth it?

Answer 1

Why is caching such a problem? In most cases, you have a local computation, so as long as you write a wrapper for the caching, you needn't worry about it. I have the following code in my utility library:

  class DroppedFunction[-A,+B](f: A => Option[B]) extends PartialFunction[A,B] {
    private[this] var tested = false
    private[this] var arg: A = _
    private[this] var ans: Option[B] = None
    private[this] def cache(a: A) {
      if (!tested || a != arg) {
        tested = true
        arg = a
        ans = f(a)
      }
    }        
    def isDefinedAt(a: A) = {
      cache(a)
      ans.isDefined
    }
    def apply(a: A) = {
      cache(a)
      ans.get
    }
  }
  class DroppableFunction[A,B](f: A => Option[B]) {
    def drop = new DroppedFunction(f)
  }
  implicit def function_is_droppable[A,B](f: A => Option[B]) = new DroppableFunction(f)

and then if I have an expensive computation, I write a function method A => Option[B] and do something like (f _).drop to use it in collect or whatnot. (If you wanted to do it inline, you could create a method that takes A=>Option[B] and returns a partial function.)

(The opposite transformation--from PartialFunction to A => Option[B]--is called lifting, hence the "drop"; "unlift" is, I think, a more widely used term for the opposite operation.)

Answer 2

Have a look at this thread, Rethinking PartialFunction. You're not the only one wondering about this.

Answer 3

This is an interesting question, and I'll give my 2 cents.

First of resist the urge for premature optimization. Make sure the partial function is the problem. I was amazed at how fast they are on some cases.

Now assuming there is a problem, where would it come from?

1. Could be a large number of case clauses
2. Complex pattern matching
3. Some complex computation on the if causes

One option I'd try to find ways to fail fast. Break the pattern matching into layer, then chain partial functions. This way you can fail the match early. Also extract repeated sub matching. For example:

Lets assume OddEvenList is an extractor that break a list into a odd list and an even list:

var pf1: PartialFuntion[List[Int],R] = { 
   case OddEvenList(1::ors, 2::ers) =>
   case OddEvenList(3::ors, 4::ors) => 
}

Break to two part, one that matches the split then one that tries to match re result (to avoid repeated computation. However this may require some re-engineering

var pf2: PartialFunction[(List[Int],List[Int],R) = {
   case (1 :: ors, 2 :: ers) => R1
   case (3 :: ors, 4 :: ors) => R2
}
var pf1: PartialFuntion[List[Int],R] = { 
   case OddEvenList(ors, ers) if(pf2.isDefinedAt(ors,ers) => pf2(ors,ers)
}

I have used this when progressively reading XML files that hard a rather inconstant format.

Another option is to compose partial functions using andThen. Although a quick test here seamed to indicate that only the first was is actually tests.

Answer 4

There is absolutely nothing wrong with caching mechanism inside the partial function, if:

1. the function returns always the same input, when passed the same argument
2. it has no side effects
3. it is completely hidden from the rest of the world

Such cached function is not distiguishable from a plain old pure partial function...