When OO and FP meet: returning the same type

In the left corner, we have Functional Programming. FP says, “Classes shall be immutable!”

In the right corner, we have Object-Oriented programming. It says, “Classes shall be extendable!”

The battlefield: define a method on the abstract class such that, when you call it, you get the same concrete class back. In Scala.
Fight!

Here comes the sample problem —

We have some insurance policies, auto policies and home policies. On any policy, you can adjust by a discount and receive a policy of the same type. Here is the test:

case class Discount(name: String)

  def test() {
    def adjust[P <: Policy](d: Discount, p: P): P = p.adjustBy(d)
    val p = new AutoPolicy
    val d = Discount(“good driver”)
    val adjustedP: AutoPolicy = adjust(d, p)
    println(“if that compiles, we’re good”)
  }

OO says, no problem!

abstract class Policy {
   protected def changeCost(d: Discount)

   def adjustBy(d: Discount) : this.type = {
       changeCost(d:Discount)
       return this
   }
}

class AutoPolicy extends Policy {
  protected def changeCost(d: Discount) { /* MUTATE */ }
}

FP punches OO in the head and says, “Mutation is not allowed! We must return a new version of the policy and leave the old one be!”[1] The easiest way is to move the adjust method into an ordinary function, with a type parameter:

object Policy {
   def adjust[P <: Policy](p: P, d: Discount): P = {
     case ap: AutoPolicy => new AutoPolicy
     … all the other cases for all other policies …
   }
}

But no no no, we’d have to change this code (and every method like it) every time we add a Policy subclass. This puts us on the wrong side of the Expression Problem.[2]

If we step back from this fight, we can find a better way. Where we declare adjustBy, we have access to two types: the superclass (Policy) and this.type, which is the special-snowflake type of that particular instance. The type we’re trying to return is somewhere in between:

How can we specify this intermediate type? It seems obvious to us as humans. “It’s the class that extends Policy!” but an instance of AutoPolicy has any number of types — it could include lots of traits. Somewhere we need to specify “This is the type it makes sense to return,” and then in Policy say “adjustBy returns the type that makes sense.” Abstract types do this cleanly:

abstract class Policy {
  type Self <: Policy
   protected def changeCost(d: Discount): Self

   def adjustBy(d: Discount) : Self = {
       changeCost(d:Discount)
   }
}

class AutoPolicy extends Policy {
  type Self = AutoPolicy
  protected def changeCost(d: Discount) = 
    { /* copy self */ new AutoPolicy }
}

I like this because it expresses cleanly “There will be a type, a subclass of this one, that methods can return.”
There’s one problem:

error: type mismatch;
 found   : p.Self
 required: P
           def adjust[P <: Policy](d: Discount, p:P):P = p.adjustBy(d)

The adjust method doesn’t return P; it returns the inner type P#Self. You and I know that’s the same as P, but the compiler doesn’t. OO punches FP in the head!

Wheeeet! The Scala compiler steps in as the referee. Scala offers us a way to say to the compiler, “P#Self is the same as P.” Check this version out:

def adjust[P <: Policy](d: Discount, p: P)
               (implicit ev: P#Self =:= P): P = p.adjustBy(d)

This says, “Look Scala, these two things are the same, see?” And Scala says, “Oh you’re right, they are.” The compiler comes up with the implicit value by itself.
The cool part is, if we define a new Policy poorly, we get a compile error:
class BadPolicy extends Policy {
  type Self = AutoPolicy
  protected def changeCost(d: Discount) = { new AutoPolicy }
}
adjust(d, new BadPolicy)
error: Cannot prove that FunctionalVersion.BadPolicy#Self =:= FunctionalVersion.BadPolicy.
           adjust(d, new BadPolicy)

Yeah, bad Policy, bad.

This method isn’t quite ideal, but it’s close. The positive is: the abstract type is expressive of the intent. The negative is: any function that wants to work polymorphically with Policy subtypes must require the implicit evidence. If you don’t like this, there’s an alternative using type parameters, called F-bounded polymorphism. It’s not quite as ugly as that sounds.

Scala is a language of many options. Something as tricky as combining OO and FP certainly demands it. See the footnotes for further discussion on this particular game.

The referee declares that FP can have its immutability, OO can have its extension. A few function declarations suffer, but only a little.

————–
[1] FP prefers to simply return a Policy from adjustBy; all instances of an ADT have the same interface, so why not return the supertype? But we’re not playing the Algebraic Data Type game. OO insists that AutoPolicy has additional methods (like penalizeForTicket) that we might call after adjustBy. The game is to combine immutability with extendible superclasses, and Scala is playing this game.
[2] The solution to the expression problem here — if we want to be able to add both functions and new subclasses — is typeclasses. I was totally gonna go there, until I found this solution. For the case where we don’t plan to add functions, only subclasses, abstract types are easier.

More references:
F-bounded type polymorphism (“Give Up Now”)
MyType problem
Abstract self types