Ad-Hoc Polymorphism and the Type Class Pattern in C#

Subtype polymorphism is not the only way to make an algorithm work across types. Sometimes you cannot change the types, do not want wrapper allocations, or need behavior selected by a generic constraint rather than a runtime hierarchy.

This article explains ad hoc polymorphism, the problems it solves, and how to model the type class pattern in C#. The technique is useful for reusable libraries and generic algorithms, but it adds generic complexity, so the tradeoff must be visible at the call site.

Ad Hoc, Subtype, and Parametric Polymorphism

We will distinguish three kinds of polymorphism:

1. Parametric polymorphism.
2. Ad hoc polymorphism.
3. Subtype polymorphism.

Let us begin with parametric polymorphism. Suppose we have a list of elements. It could be a list of integers, floating-point numbers, strings, or anything else. Now imagine a GetHead() method that returns the first element of the list. It does not care whether the returned element is an int, string, Apple, or Orange. Its return type is the formal type parameter represented by T in IList<T>, and its implementation is the same for every type: "return the first element."

interface IList<T>
{
    T GetHead();
}

Unlike parametric polymorphism, ad hoc polymorphism depends on the type. The type determines which of several implementations is called. Method overloading is one example. You can have two versions of a method that joins one value to another: one accepts two integers and adds them, while the other accepts two strings and concatenates them. You know that 2 + 3 = 5, but "2" + "3" = "23".

class Appender
{
    public int AppendItems(int a, int b) =>
        a + b;

    public string AppendItems(string a, string b) =>
        $"{a}{b}";
}

With subtype polymorphism, derived classes provide different implementations of a method from a base class. Ad hoc polymorphism decides which implementation to call at compile time—early binding—whereas subtype polymorphism makes that decision at runtime—late binding.

abstract class Animal
{
    public abstract int GetMeatMass();
}

class Cow : Animal
{
    public override int GetMeatMass() => 20;
}

class Dog : Animal
{
    public override int GetMeatMass() => 5;
}

Now let us examine ad hoc polymorphism more closely and leave the other two kinds for another time. As noted above, method overloading is one way to achieve it: each version accepts different parameters, and the call selects the appropriate implementation from their types. But imagine a different scenario. We want only one method, which we can call AppendItems(), that accepts two "appendable" values. With integers, it should combine them through arithmetic addition. With strings, it should combine them through concatenation. We could define behavior for many other types, but int and string are enough for this example.

The brute-force solution is to write an overload for every data type, but we would rather make the compiler help us without creating hundreds of methods.

class Appender
{
    public int AppendItems(int a, int b) =>
        a + b;

    public string AppendItems(string a, string b) =>
        $"{a}{b}";

    public bool AppendItems(bool a, bool b) =>
        a || b;
}

The C# Problem: Combining Unrelated Types

We need AppendItems() to accept two instances of something "appendable" and combine them. The combine operation must also have different implementations for different appendable objects: addition for integers and concatenation for strings. This is a perfect example of ad hoc polymorphism.

Notice that the method must have only one implementation—no overloading or overriding. How can it perform different operations for different types? The idea is that AppendItems() should not know how the append operation is implemented. It should simply invoke it. Here is the method:

class Appender
{
    T AppendItems<T>(T a, T b) => a.Append(b);
}

This is the difficult part: we need to obtain an append operation for integers and strings. How? From the perspective of AppendItems(), they will not be integers or strings. They will be something "appendable." In essence, this is behavioral duck typing: if it walks like a duck and quacks like a duck, we treat it as a duck. We do not care what it is; we care only that it can quack. Here, instead of requiring values to quack, we require them to append.

The method above will not compile because the generic type T has no Append() method. What can we do? I will explain two approaches: wrapper types and the type class pattern.

Wrapper Types as an Adapter

To convince the compiler that T is appendable, we can use a wrapper-type approach built from familiar C# mechanisms. Then we can implement AppendItems() much like the version shown above.

class Appender
{
    public T AppendItems<T>(AppendableValue<T> a, AppendableValue<T> b) =>
        a.Append(b);
}

This method says, "I take two AppendableValue<T> elements and append them." The compiler replies, "Fine. I will let you call Append() on an AppendableValue<T> because you promised that it would have such a method, and I am holding you to that promise." If the method does not exist at compile time, the compiler will be unhappy, to put it mildly, and compilation will fail.

Now that we have AppendItems(), let us move on to AppendableValue<T>.

First, AppendableValue<T> will be an abstract class. An abstract class is convenient for implementing a wrapper type when you need to pass parameters to a base-class constructor, inherit it in C# code, and so on.

Second, AppendableValue<T> will be parameterized: it has a formal type parameter. Why? Because its Append() operation—not to be confused with our AppendItems() method—is generic. It will be implemented differently for different types: addition for integers and concatenation for strings. Because Append() depends on the type, the entire abstract class depends on the type. If it did not, this would be parametric polymorphism. Because it does, this is ad hoc polymorphism.

Here is our small wrapper type, implemented as an abstract class:

abstract class AppendableValue<T>
{
    public T Value { get; }

    protected AppendableValue(T value) =>
        Value = value;

    public abstract T Append(AppendableValue<T> item);
}

Now that the wrapper type is defined, let us write two implementations: one for int and one for string.

class AppendableIntValue :
    AppendableValue<int>
{
    public AppendableIntValue(int value) :
        base(value)
    {
    }

    public override int Append(AppendableValue<int> item) =>
        Value + item.Value;
}

class AppendableStringValue :
    AppendableValue<string>
{
    public AppendableStringValue(string value) :
        base(value)
    {
    }

    public override string Append(AppendableValue<string> item) =>
        $"{Value}{item.Value}";
}

The string interpolation is only for demonstration. I could simply—and more conventionally—write Value + item.Value, which would combine them just as well. I deliberately wanted AppendableStringValue to look different from AppendableIntValue to emphasize that the implementation is type-specific.

That was not difficult, was it? We can now pass ordinary wrapper instances to AppendItems(), and the code type-checks. Here is everything in use:

var appender = new Appender();
Console.WriteLine(
    appender.AppendItems(
        new AppendableIntValue(1),
        new AppendableIntValue(2)));
Console.WriteLine(
    appender.AppendItems(
        new AppendableStringValue("1"),
        new AppendableStringValue("2")));

Implementing the Type Class Pattern in C

Wrapper classes were fun, but type classes are even more interesting. They are more flexible and therefore more powerful. Do not take my word for it—read on and see for yourself.

The type class concept originated in Haskell. Given what we know so far, the simplest explanation is this: rather than wrapping values in AppendableIntValue and AppendableStringValue to perform an operation, separate types provide the operation for those values. In essence, this separates data from operations.

That means we need to change AppendItems() slightly. It still accepts two elements to combine, but instead of a wrapper type, it now needs the type class for the appendable type. The closest C# description would be the following impossible code:

class Appender
{
    public T AppendItems<IAppendable<T>>(T a, T b) =>
        IAppendable.Append(a, b);
}

Unlike Haskell, C# has no built-in type class construct, so we have to model it—much as we model monads. The usual approach is to define a type-class interface and implement it for different concrete type parameters. Here are a few lines of code that demonstrate the concept:

interface IAppendable<T>
{
    T Append(T a, T b);
}

struct AppendableInt : IAppendable<int>
{
    public int Append(int a, int b) =>
        a + b;
}

struct AppendableString : IAppendable<string>
{
    public string Append(string a, string b) =>
        $"{a}{b}";
}

There it is: an IAppendable<T> interface and two implementations, AppendableInt and AppendableString.

One powerful property of type classes is that they make it easy to extend libraries without access to their source code. To support types other than int and string, you only need to provide new implementations. You can also provide alternative implementations for existing types—for example, appending integers by multiplication instead of addition.

struct AppendableIntMultiplicative : IAppendable<int>
{
    public int Append(int a, int b) =>
        a * b;
}

The next question is how to modify AppendItems() to use IAppendable<T>. You may have noticed that every interface implementation is a struct, declared with struct. In a generic context, this lets us create instances with the default operator and zero allocation cost. Creating an instance of the appendable type class costs nothing. The tradeoff is that we need two formal type parameters.

class Appender
{
    public T AppendItems<TAppendable, T>(T a, T b)
        where TAppendable : struct, IAppendable<T> =>
        default(TAppendable).Append(a, b);
}

Here is how to use it:

Console.WriteLine(appender.AppendItems<AppendableInt, int>(1, 2));
Console.WriteLine(appender.AppendItems<AppendableString, string>("1", "2"));

When to Use Type Classes in C

C# expresses ad hoc polymorphism through method overloading. The supplied type determines which method implementation is selected, so the compiler helps us through early binding. If we want it to keep helping while using a single generic contract instead of many overloads, we can reach for the powerful type class pattern from functional programming. In C#, it is implemented by separating operations from data.

P.S.

In addition to this article, there is a proposal in the dotnet repository and the language-ext library, both of which contain more interesting examples:

• github.com/dotnet/csharplang/issues/110
• github.com/MattWindsor91/roslyn/blob/master/concepts/docs/csconcepts.md
• github.com/louthy/language-ext

Follow StepOne on GitHub for open-source C#/.NET projects, compiler experiments, production-focused examples, and new releases.