# 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."

```csharp
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"`.

```csharp
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.

```csharp
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.

```csharp
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:

```csharp
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.

```csharp
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:

```csharp
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`.

```csharp
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:

```csharp
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:

```csharp
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:

```csharp
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.

```csharp
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.

```csharp
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:

```csharp
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](https://github.com/dotnet/csharplang/issues/110)
    
*   [github.com/MattWindsor91/roslyn/blob/master/concepts/docs/csconcepts.md](https://github.com/MattWindsor91/roslyn/blob/master/concepts/docs/csconcepts.md)
    
*   [github.com/louthy/language-ext](https://github.com/louthy/language-ext)
    

Follow [StepOne on GitHub](https://github.com/Stepami) for open-source C#/.NET projects, compiler experiments, production-focused examples, and new releases.