Most OO programmers have come across this situation: you have some types that don’t share any common supertype, but you wish they did, so you could write some generalized code that works for both types.

For example, you have a CartoonDuck and a RubberDuck class, they both quack, but you didn’t design them to implement a common Duck interface. So it makes it hard for you to create your duck utility library that works with all kind of Ducks.

Ill-Conceived Duck Library

The obvious solution is just to modify the original library code, and make the two duck classes implement a common Duck trait. But let’s say we can’t or don’t want to (e.g. we don’t have commit privileges for the Duck class library, or it is on a long release cycle).

The ability to extend functionality of a library without modifying its source is known as Retroactive Extension. Doing so without creating wrappers has been called Retroactive Polymorphism. There are a couple of great posts by Casual Miracles and Daniel Westheide that talk about using Type Classes in Scala to achieve retroactive polymorphism.

I would classify the particular kind of retroactive extension required for the Duck library — creating a common supertype for some classes without modifying their original code — as retroactive supertyping

In this post I’ll explore various techniques for achieving retroactive supertyping. But for the impatient, I’ll skip to the end with a comparison of pros/cons for each:

Comparison

Let’s start with our base class library.

class CartoonDuck(saying: String) {
    def quack(): String = saying
}

class RubberDuck {
    def quack(): String = "Squeek!"
}

val donald = new CartoonDuck("What’s the big idea?")
val daffy = new CartoonDuck("You’re dispicable!")
val rubberDucky = new RubberDuck()

/* Todo, implement describeDuckCollection and use it  */
//def describeDuckCollection(ducks: List[Duck]) { /* implement */ }
//describeDuckCollection(List(donald, daffy, rubberDucky))

But, we can’t implement describeDuckCollection(ducks: List[Duck]), because the Duck class doesn’t exist…

Solution 1: Modify Original Code

Again, often the best solution, but suppose we don’t want to do this.

Solution 2. The Adapter Pattern

Okay, so let’s create a Duck trait and create two adapter classes. This is usually a perfectly acceptable solution, especially if your code will be called from Java code that can’t use implicits, or maintained by Java programmers that don’t like implicits. The main drawback is it requires clients of your duck utility library to write extra code to wrap their ducks.

trait Duck {
    def quack(): String
}

def cartoonDuckAsDuck(d: CartoonDuck): Duck = new Duck { def quack() = d.quack() }

def rubberDuckAsDuck(d: RubberDuck): Duck = new Duck { def quack() = d.quack() }

def describeDuckCollectionUsingWrappers(ducks: List[Duck]) {
    print(
        "Here are my ducks: " +
        ducks.map(duck => "\tA duck that says ‘" + duck.quack() + "’").mkString("\n","\n","\n")
    )
}

val wrappedDonald = cartoonDuckAsDuck(donald)
val wrappedDaffy = cartoonDuckAsDuck(daffy)
val wrappedRubberDucky = rubberDuckAsDuck(rubberDucky)

describeDuckCollectionUsingWrappers(List(wrappedDonald, wrappedDaffy, wrappedRubberDucky))

Solution 3: The Rich Wrapper Pattern (or Pimp My Library Pattern)

If you don’t like explicitly creating those wrappedDonald, wrappedDaffy, etc. objects, then you can make your code more terse and at the same time more mystifying to newbie Scala developers — so they will respect you for your erudition even if they can’t work with your code ;) — by using the Rich Wrapper pattern and implicit conversions.

/* Create a companion object to the Duck trait with the implicit conversion functions.  Names of the functions don’t matter, only signatures. */
object Duck {
    implicit def cartoonDuckAsDuck(d: CartoonDuck): Duck = new Duck { def quack() = d.quack() }
    implicit def rubberDuckAsDuck(d: RubberDuck): Duck = new Duck { def quack() = d.quack() }
}

def describeDuckCollectionUsingWrappersAndImplicitConversions(ducks: List[Duck]) {
    print(
        "Here are my ducks: " +
        ducks.map(duck => "\tA duck that says ‘" + duck.quack() + "’").mkString("\n","\n","\n")
    )
}

describeDuckCollectionUsingWrappersAndImplicitConversions(List(donald, daffy, rubberDucky))

Here, the caller doesn’t have explicitly wrap its ducks — Scala wraps them for you automatically! If the types of objects being passed to a function don’t match the required types, Scala will look for implicits, functions that can convert them to the right types. It will look for any methods marked implicit in the current scope, or in any relevant companion objects — in this case, the Duck object — and if it finds one with the right type signature, it will assume you want to use it to convert your object to the right type, and do it for you automatically.

Solution 4: Structural Types

With structural types, I can retroactively create a supertype, and declare that anything that declares the quack() method of the right signature is an instance of that type.

/* If it quacks, it’s a duck */
type StructuralDuck = {def quack(): String}

def describeDuckCollectionUsingStructuralType(ducks: List[StructuralDuck]) {
    print(
        "Here are my ducks: " +
        ducks.map(duck => "\tA duck that says ‘" + duck.quack() + "’").mkString("\n","\n","\n")
    )
}

describeDuckCollectionUsingStructuralType(List[StructuralDuck](donald, daffy, rubberDucky))

This one is simple, doesn’t require client code to explicitly wrap objects, and doesn’t use implicits! It seems like a perfect solution!

But, structural types only work if your classes all happen to have a duck method with the right signature.

And although structural types are considered to be type safe, they are not not necessarily semantically type safe. Even though it’s probably safe to say that anything that has a quack method is a duck, in other cases, two classes sharing a method with a common name could be mere coincidence. For example, I can create a structural type {def open(): ()}, and it would automatically be a common supertype for both Files and a Doors, but it would be useless and potentially dangerous. So, just keep that in mind.

Solution 5: Type Class Pattern

Type classes, the go-to solution for retroactive extension in Haskell, are probably overkill for the simple problem we are trying to solve here.

Type classes have many of the same pros/cons as the Rich Wrapper pattern, but are more powerful because they allow for multiple dispatch. Our retroactive duck supertyping challenge doesn’t require multiple dispatch, but I’ll still show how the type class pattern would be used in this example.

trait DuckTypeClass[D] { def quack(d: D): String }

object DuckTypeClass {
    implicit def cartoonDuckService: DuckTypeClass[CartoonDuck] = new DuckTypeClass[CartoonDuck] { def quack(d: CartoonDuck) = d.quack() }
    implicit def rubberDuckService: DuckTypeClass[RubberDuck] = new DuckTypeClass[RubberDuck] { def quack(d: RubberDuck) = d.quack() }
}


def describeDuckCollectionUsingTypeClass[D: DuckTypeClass](ducks: List[D]) {
    print(
        "Here are my ducks: " +
        ducks.map(duck => "\tA duck that says ‘" + implicitly[DuckTypeClass[D]].quack(duck) + "’").mkString("\n","\n","\n")
    )
}

So understand that here, unlike with the Adapater pattern, we are not creating wrapped Duck objects that implement some kind of Duck trait. Instead we are creating objects that are like services (called type class instances) that provide a static duck function, taking CartoonDucks or RubberDucks as arguments. We create just one instance of each of these services for each type of duck, and pass them implicitly to describeDuckCollectionUsingTypeClass.

Notice the : DuckTypeClass inside the type parameter. This is a context bound, which is syntactic sugar, essentially equivalent to defining the method signature as:

def describeDuckCollectionUsingTypeclass[D](ducks: List[D])(implicit duckService: DuckTypeClass[D])

And then

implicitly[DuckTypeClass[D]].quack()

is also syntactic sugar, equivalent to writing

duckService.quack()

And to be precise, Scala will choose some unique name for the parameter, not necessarily duckService.

Okay, basically we create services that give us static quack and other duck-like functionality, we pass them implicitly to general purpose duck code, and use the context-bound implicit parameter to make method signature a little more terse.

The Heterogeneous Collection Problem

But there’s a problem. Even though this works:

describeDuckCollectionUsingTypeClass(List(donald, daffy))

The following will give you a horrid little error that will make you wonder if it was all worth it:

describeDuckCollectionUsingTypeClass(List(donald, daffy, rubberDucky))

Output

error: could not find implicit value for evidence parameter of type this.DuckTypeClass[ScalaObject]
describeDuckCollectionUsingTypeClass(List(donald, daffy, rubberDucky))
                                    ^

So what’s going on? Well, the first function call works, because, the List only contains CartoonDucks. So Scala infers the type of the argument to be List[CartoonDuck]. It then looks for a typeclass instance of type DuckTypeClass[CartoonDuck], which it finds in the DuckTypeClass companion object. So all good

In the second function call, since the list contains two different types of Duck objects, Scala infers the type to be List[ScalaObject] — the common supertype of RubberDuck and CartoonDuck. But, we can only implicitly pass one instance of DuckTypeClass[D] — either DuckTypeClass[CartoonDuck] or DuckTypeClass[RubberDuck]. Thus, failure!

Solution 6: Hybrid Type Class with Structural Type

However, ScalaObject isn’t the only common supertype of CartoonDuck and RubberDuck. We already defined the StructuralDuck type previously! So let’s just create a new type class instance for StructuralDucks in the DuckTypeClass companion object!

object DuckTypeClass {
  implicit def structuralDuckService: DuckTypeClass[StructuralDuck] = new DuckTypeClass[StructuralDuck] {
    def quack(d: StructuralDuck) = d.quack()
  }
}

Then we suddenly can deal with heterogenous collections! Because Scala can deduce the list we are passing to be an instance of List[StructuralDuck], and it can find an implicit instance of DuckTypeClass[StructuralDuck], the call will work:

describeDuckCollectionUsingTypeClass(List(donald, daffy, rubberDucky))

Multiple Dispatch and Type Classes

But why would we want to do this? Aren’t we overcomplicating things? We had a perfectly good solution with structural types alone — why use structural types AND type classes?

The answer is, we wouldn’t. Don’t use a type class in cases like this. It’s overkill.

But let me show you when you would need a typeclass. Suppose we want our ducks to fight.

The trick is, the fight method takes two ducks as parameters, and the outcome of the fight depends on the type of duck. If we add the fight method to the type class instances cartoonDuckService and rubberDuckService, we have a problem. Only ducks of the same type could fight:

trait DuckTypeClass[D] { def quack(d: D): String; def fight(d1: D, d2: D): D }

object DuckTypeClass {
    implicit def cartoonDuckService: DuckTypeClass[CartoonDuck] = new DuckTypeClass[CartoonDuck] {
        def quack(d: CartoonDuck) = d.quack()
        def fight(duck1: CartoonDuck, duck2: CartoonDuck)
    }

}

But using a type class and a structural type, any two objects with a quack method can fight.

object DuckTypeClass {
    implicit def structuralDuckService: DuckTypeClass[StructuralDuck] = new DuckTypeClass[StructuralDuck] {
      def quack(d: StructuralDuck) = d.quack()

      /* Define a fight method that works for any two structural ducks */
      import scala.util.Random
      def fight(blueCorner: StructuralDuck, redCorner: StructuralDuck): StructuralDuck = (blueCorner, redCorner) match {

        /* Cartoon Ducks beat Rubber Ducks */
        case (rubberDuck: RubberDuck, cartoonDuck:CartoonDuck) => cartoonDuck

        /* Obviously, order of parameters doesn’t matter */
        case (cartoonDuck:CartoonDuck, rubberDuck: RubberDuck) => fight(rubberDuck, cartoonDuck)

        /* For other combinations of ducks, let fate decide */
        case (duck1, duck2) => if((new Random()).nextBoolean) duck1 else duck2
      }
    }
}

def describeDuckCollectionUsingTypeClassAndMultipleDispatch[D: DuckTypeClass](ducks: List[D]) {

    /* Import quack and fight from the typeclass instance */
    val duckService = implicitly[DuckTypeClass[D]];
    import duckService._

    print(
        "Here are my ducks: " +
        ducks.map(duck => "\tA duck that says ‘" + quack(duck) + "’").mkString("\n","\n","\n")
    )
    print(
        "They are fighting!  The winner says: " + quack(ducks.reduce(fight))
    )
}

describeDuckCollectionUsingTypeClassAndMultipleDispatch(List[StructuralDuck](donald, daffy, rubberDucky))

Now to be clear, what are the benefits of this solution? It means that now, we can create new Duck types, create a DuckTypeClass instances for them, and include them in our duck collection, and all of our describeDuckCollection* code will still work. And we can do this all without touching either our original library code, or the describeDuckCollection implementations! If you are a fan of the open-closed principle, and like to extend functionality with modifying perfectly good code, that’s nice.

Comparison

So each method has its pros and cons, like everything in life! I hope that this simple comparison will help you decide which solution will work best for your particular needs.

Comparison

3 Comments

  1. John Glassmyer
    July 23, 2013

    Leave a Reply

    I must have missed something. Your table comparing the different methods at the end says that Hybrid does not depend on method names. How is this the case when your example uses a structural type requiring a “quack” method?

    • john.warden@gmail.com
      July 23, 2013

      Leave a Reply

      John, you are right! That was a mistake. I’m going to update that diagram.

  1. This week in #Scala (22/07/2013) | Cake Solutions Team Blog - [...] Jonathan Warden blogged: Retroactive Supertyping in Scala [...]

Leave a Reply

*



You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>