Bend any type to your will with ad-hoc polymorphism

9 min readNov 2, 2018

According to Wikipedia[¹], polymorphism in programming languages and type theory is:

the provision of a single interface to entities of different types or the use of a single symbol to represent multiple different types

The idea behind polymorphism is simple: to increase code reuse by writing it in a more generic fashion. There are 3 main forms of polymorphism that we can use, namely:

subtype polymorphism (inheritance)
parametric polymorphism (generics)
ad-hoc polymorphism (type classes)

In this article we will use Scala to explore the first 2 types of polymorphism including their use-cases as well as their limitations. Then, we will examine the power and flexibility of ad-hoc polymorphism through type classes and how it rises to the challenge in areas where the others fall short.

Subtype Polymorphism

Subtype polymorphism is the polymorphism that you get from inheritance as you know it from object oriented programming. More formally, subtype polymorphism allows a function to take an argument of type T but will also work when given an argument of type S that is a subtype of T. This is also known as the Liskov substitution principle[²].

For example, suppose we have the following hierarchy for the menus of different restaurants:

We can then define a method that orders food from a Restaurant's menu:

With subtype polymorphism, we’re able to treat whole groups of types (eg. restaurants in our example) the same since they all implement the same behaviors despite having different implementations of these behaviors. That is to say, we can order food from Mexican, Italian, and Chinese restaurants because all Restaurants have a menu, even if the food they make is not the same.

Parametric Polymorphism

Parametric polymorphism allows a function or data type to be written generically so that it can handle values of any type by not relying on the type itself. In other words, parametric polymorphism allows you to treat all types in the same manner regardless of the fact that these types might be different from one another.

Let’s say that we wanted to implement a custom Set type:

What type can we use for the values of our set? One option would be to use a top-level type like Scala’s Any (which is similar to Java's Object):

The downside of this approach is that we need to do a lot of runtime type checking and casting to make things work:

Another option would be to define separate versions of our set for each type that we want to support:

This can quickly get out of hand as it involves a lot of duplicate code that does not differ across types. Notice that we’re not implementing any type-specific behavior. Rather, all we are doing is just adding and removing elements to a set without acting on the elements themselves.

Because of this, we can use parametric polyorphism to abstract the type of our Set and treat it as a template:

This allows us to reduce boilerplate by writing code that can work uniformly with different types such as Doubles and Strings:

Ad-Hoc Polymorphism

The term ad hoc polymorphism was originally coined by Christopher Strachey to refer to functions that can be applied to arguments of different types, but that behave differently depending on the type of the argument they are given. In this case the term “ad hoc” refers to the fact that this type of polymorphism is not a fundamental feature of the type system of the programming language[³].

Another way to think of this is that we can use ad-hoc polymorphism to define behavior across different unrelated types where the implementation of the behavior is specific to each type.

To better understand this, let’s look at an example.

Use case — A bakery

Suppose we’re opening a bakery and we need to build an application to calculate the shelf life of the bread we’re going to sell. Shelf life for baked goods typically depends on things like the day they were made, the ingredients that were used, whether or not things were refrigerated, etc.

In this case, we need to implement a common behavior (calculating the expiration date) across different types of baked goods so that we know when we need to make new batches. Naturally, from the name of this section, ad-hoc polymorphism will be the way to go. But first, let’s explore some of our other alternatives.

Subtype Polymorphism

One approach is to use subtype polymorphism by defining a top-level Perishable type that the types of our different baked goods can inherit from:

Then from one of the services in our application, we would use this top-level Perishable type to find all of the bread that expired so we can replace it with a fresh batch on a daily basis:

This approach presents a few problems:

With subtype polymorphism we lose type information that might have otherwise been useful. For example, if we pass in a list of Baguettes to our needsReplacing function, we get back a list of Perishables. In other words, we lose context about the type of baked goods that expired which makes it hard to know if we need to bake more baguettes or more croissants.
We also close our API to future extension for types that we don’t control. For example, imagine that one day we enter into a partnership with an ice cream shop and we expand the menu to include ice cream. As part of the deal, the ice cream shop provides us with a custom Scala library (compiled in a jar) for managing their product which includes an IceCream type. By using subtype polymorphism to model food expiration, we would not be able to extend IceCream with Perishable like we did for our other menu items since IceCream belongs to source code we don't have access to.

Adapter Pattern (ie. Parametric Polymorphism)

Another option would be to use the adapter pattern. The adapter pattern is used to make existing types work with others by wrapping them in a new interface.

In this case, we can create a PerishableLike interface to wrap all the types of baked goods in our bakery:

Then, we can parameterize our function on some type T and use a list of PerishableLike[T] as both its input parameter type and its return type:

While this approach gives us full type safety and extensibility (you’ll notice that we were even able use it with the IceCream type), it does come with its downsides:

By wrapping our types inside another PerishableLike[A] type, we incur the performance hit of having to allocate extra memory. The larger the list of menu items we need to find the expiration for, the more adapter instances we have to create.
Currently, we only have a single behavior (calculating expiration) that is common across our menu. But what if in the future, we need to implement another set of behaviors? For example, we might want to categorize our menu by figuring out which items meet certain dietary restrictions such as being gluten free. At this point we have 2 options:

We can create a new adapter type every time we need a new behavior and deal with ever increasing memory costs from using multiple wrappers for the same menu item.
Or we can refactor PerishableLike into a more generic FoodLike adapter where we define all of the common behaviors we need to support across our menu. This tight coupling, however, will lead to bloated adapters that make behaviors hard to compose, maintain, and test.

Ad-hoc polymorphism, which is implemented through type classes in Scala, solves these problems.

Type Classes

Type classes are a programming pattern that originated in Haskell. They allow us to extend existing code with new functionality without using inheritance and without altering the original source code.

Scala does not offer built-in support for type classes at the language level but, we can use a combination of generics and implicits to model them. There are 3 main components of the type class pattern:

the type class itself,
the type class instances, and
the type class interface

The Type Class

A type class is a construct that represents some behavior or functionality that we want to implement across different types. In Scala, a type class is represented as a trait parameterized on some type T.

Continuing with our bakery example, we can create a type class called Perishable to determine if our baked goods have expired:

Instances

The instances of a type class provide implementations of the trait for the types we care about. These types can include not only your own custom types but also types from the Scala standard library as well as types defined in other 3rd party libraries.

In Scala, we define instances by creating concrete implementations of the type class and tagging them with the implicit keyword in order for them to become implicitly available when we need them.

Using the types from our menu:

We can define some instances for our Perishable type class:

Interface

Finally, we can refactor our needsReplacing method from earlier and have it serve as the "interface" for our type class. First, we parameterize it on some type T and then we define a new implicit parameter group for our Perishable type class:

Now, to find the baguettes that expired, we first import the type class instance for our Baguette type and then we call the needsReplacing method by passing it a list with our baguettes:

When we call the needsReplacing method with a list of baguettes, our type parameter T gets bound to our Baguette type. Since we didn't specify any arguments for the implicit paramter, the compiler searches the implicit scope for an instance of Perishable[Baguette] and finds our baguettePerishable instance.

Expanding the menu

Going back to our new partnership with the ice cream shop, how would we support calculating the expiration for ice cream?

Since our needsReplacing method needs an implicit instance of the type that it's going to calculate the expiration for, all we need to do is create a new type class instance for the IceCream type:

And bring it into the implicit scope just like before:

That’s all there’s to it. That’s the power of type classes. You can arbitrarily extend any type, including types you don’t control, with new behavior at a moment’s notice. All you need to do is simply define a new instance of the type class that implements the behavior you want and bring it into scope.

Adding new behaviors

We know what to do if we decided to expand the menu again to include, say, sandwiches. But what if we wanted to add new behaviors across our menu like we did with expiration?

Imagine that we want to start accomodating clientele with more diverse dietary needs. For example, say that we want to categorize our menu so that we can tell our customers which items are gluten-free.

To do this, we first define a new type class like we did earlier for Perishable and then we create type class instances for the menu items that we want to categorize:

Next, we create a new method that uses an implicit parameter for our new type class:

And voila! Now, we can better serve customers that are gluten intolerant. We didn’t need to wrap our types inside another type like we would have had to do with adapters. To support additional cross-type functionality going forward, we can continue with this approach of defining new type classes. Then, we simply parameterize the methods that need this functionality and bring the appropriate type class instances into scope.

We can also define more than one implicit type class parameter in our methods which allows us to effectively compose multiple behaviors together. For example, imagine we wanted to support customers that were both gluten AND lactose intolerant. After defining a new type class (and type class instances) for this new behavior:

We can define a new method that takes 2 implicit parameters for each dietary restriction that we need to account for:

With type classes we’re able to compose different behaviors together to support our ever-growing business needs.

Final Thoughts

Type classes are a very powerful construct that allow us to encode ad-hoc polymorphism in Scala. With them, we can support the same behaviors across unrelated types without resorting to inflexible approaches like inheritance and without incurring a performance penalty like we do with the adapter pattern. Furthermore, we can easily compose multiple behaviors together while keeping them self-contained. This allows us to create programs that require complex functionality without sacrificing modularity and maintainability.

Thanks for reading!