Ad-hoc-polymorphism and type class pattern in C#

Ad-hoc-polymorphism and type class pattern in C#

This article explains what ad-hoc polymorphism is, what problems it solves, and how to implement it in general, using the type class pattern in the C# programming language.

▍ Types of polymorphisms

It turns out that there are at least three types of polymorphisms:

  1. Parametric.
  2. Special (ad-hoc).
  3. Polymorphism of subtypes.

Let’s start with

parametric polymorphism

. Let’s say we have a list of elements. It can be a list of integers, floating point numbers, strings, whatever. Now imagine the method

GetHead()

, which returns the first element from this list. It doesn’t care if the returned element is a type

int

,

string

,

Apple

or

Orange

. Its return type is a formal default parameter

T

within

IList<T>

and its implementation

the same

to all types: “return the first element”.

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

Unlike parametric polymorphism,

special polymorphism

bound to type. Depending on it, they are called

different implementations

method Method overloading is one example of ad-hoc polymorphism. For example, you can have two versions of the method that joins the first element to the second – one that takes two integers and adds them, and another that takes two strings and concatenates them. You know what

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}";
}

At

polymorphism of subtypeschild classes

provide different implementations of the method of some

basic class

. Unlike custom polymorphism, where the decision about which implementation is called is made at compile time (early binding), subtype polymorphism is made 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’s take a closer look at ad-hoc polymorphism, we will not consider the other two in detail this time. As mentioned earlier, method overloading is one way to achieve ad hoc polymorphism: each “version” of a method will accept different parameters, and the correct implementation will be chosen when the method is called, given the type of parameters provided. But let’s say there’s another scenario—let’s say we want to have just one method (we can call it

AppendItems()

), and want this method to accept two “joining” elements. If called with integers, they must be concatenated using arithmetic addition. If called with strings, they must be joined using concatenation. One can invent implementations for various other types, but for our example

int

and

string

will be enough.

Of course, there is an option to solve the problem “head on” – to write a load for each data type, but we would like to make the compiler help us without creating 100,500 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;
}

▍ How to connect ducks

Therefore, it is necessary that the method

AppendItems()

took two instances of something “joins” and performed a join operation on them. It is also required that this operation have different implementations for different “joining” objects. For integers – addition, for strings – concatenation. This is the best example of ad hoc polymorphism.

Note that a method must have only one implementation – no overloading or overriding! How can it perform different operations for different types? So the idea is that the method AppendItems() does not even need to know how the join operation is implemented; he just has to summon her. Here is the method itself:

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

This is the most difficult part — you have to somehow get the operation of concatenating integers and strings. As? Nevertheless, in the eyes of our method

AppendItems()

they will not be integers and strings. They will be something that “joins”. This is, in fact, an example

duck typification

by behavior: if it walks like a duck and quacks like a duck, we think it’s a duck. We don’t care that it’s actually all we care about is that it can croak. That’s what we’ll do here, only instead of the values ​​being able to quack, we need them to be able to join.

Of course, the method above does not compile, as it does with a generalized type T there is no method Append(). And what to do here? I’ll explain two approaches to this problem—container types and the type class pattern.

▍ Container types

To convince the compiler that the type

T

really joins, you can use a containerized type approach that uses fairly common C# mechanisms. Then it will be possible to implement the method

AppendItems()

in a similar way as shown above.

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

This method says, “I take two elements of type

AppendableValue<T>

and join them.” The compiler responds, “Okay, I’ll let you call the method

Append()

on the type value

AppendableValue<T>

because you promised he would have a method

Append()

, and I rely on it.” If it’s not there at compile time, the compiler will be mildly displeased because the promise is broken and the compilation will fail.

Okay, the method AppendItems() received Let’s go to the type AppendableValue<T>.

First, AppendableValue<T> will be an abstract class. First of all, it is quite convenient to use an abstract class to implement a container type, if you need to pass some parameters to the constructor of the base class, some C # code will inherit it, and so on.

Second, AppendableValue<T> will be parameterized – it will have a formal default parameter. Why? Well, because his surgery Append() (not to be confused with our method AppendItems()!) is generalized. She will be implemented differently for different types, in the case of both addition of integers and concatenation for strings. Since the method Append() depends on the type, an abstract class depends on the type. Note that if it did not depend on the type, it would be a case of parametric polymorphism, but since it depends, it is a case of special polymorphism.

Here’s our cute little container type implemented using 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 we have a container type definition, let’s write two different implementations for it: one for

int

and another for

string

. Here they are:

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}";
}

String interpolation is here for demonstration purposes – I could (and usually do) just write

Value + item.Value

which would also tie them together nicely, but I specifically wanted to

AppendableStringValue

differed from

AppendableIntValue

To emphasize that the implementation is specific to each type.

All in all, it was easy, wasn’t it? Now we can pass regular instances of container types AppendItems(), and everything will pass type checking. Here’s the actual code using all the work:

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

▍ Pattern type class

Container classes were fun. However, it’s even more fun with the type class pattern – it’s more flexible and, therefore, more powerful. But instead of taking my word for it, read on and see for yourself.

Type class is a concept that originated in Haskell. The easiest way to describe it in terms of what we know so far is that instead of packing values, container types AppendableIntValue and AppendableStringValue To perform an operation on them, the types themselves would offer the ability to perform an operation on them. In essence, this is the separation of data from the operation.

This means we need to change our method a bit AppendItems(). It still accepts two elements to join, but instead of a container type, it now requires a class of the type being joined. The closest C# description would be the following code, although it’s not possible:

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

Unlike Haskell, type classes are not an existing C# structure and must be modeled (like monads, for example). This is usually done by defining an interface of a class type that implements various specific type parameters. Let me give you a few lines of code that demonstrate this concept in all its glory:

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}";
}

Do you see? There is an interface

IAppendable<T>

and its two implementations:

AppendableInt

and

AppendableString

.

One of the cool things about type classes is that it’s easy to extend libraries without having access to their source code. For example, if you want to support some types other than int and string, you only need to provide new implementations of these types. In addition, it is possible not only to provide implementations for new types, but also to override implementations for existing types, for example to concatenate integers using multiplication instead of addition.

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

Then the question arises: how to refine the method

AppendItems()

to use the interface

IAppendable<T>

? As you may have noticed, all interface implementations are created as structs using the keyword

struct

. This allows you to create instances of such objects in a generalized environment using the operator

default

and zero cost allocation. That is, creating an instance of the type class that joins is worthless! However, for this you need to use two formal typical parameters.

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

And this is how it is used.

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

▍ Conclusion

Ad-hoc polymorphism is exposed in the C# programming language through method overloading. Depending on the substituted type, the required implementation of the method is selected, that is, the compiler helps us in early binding. To make it continue to help us by having one universal contract instead of many loads, there is a powerful type class pattern from the world of functional programming implemented in C# by separating the operation from the data.

▍ PS

By the way, in addition to this article, there is a proposal in the dotnet repository and the language-ext library, where you can find more interesting examples:

I also run a Telegram channel

StepOne

where I teach a lot of interesting content about commercial development, C# and the world of IT through the eyes of an expert.

Telegram channel with prize draws, IT news and posts about retro games 🕹️

Related posts