Existentially quantified types in C#
Tags: csharp, dotnet, functional
Published: 2020-03-15 15:57:43

#Emulating first-class polymorphism

[Last time](https://dev.to/shimmer/c-generic-type-brainteaser-2lk1), we talked about universally quantified types and the challenge of passing a generic function to a non-generic function. The best way to do this is with a non-generic interface that contains one or more generic methods. This allows us to limit the scope of the type variables to each method. In our case, we can define an interface that represents operations on generic lists:

```csharp
interface IListOperations
{
    int GetWeight<T>(IList<T> items);   // scope of T is limited to GetWeight
    // ... other methods with other type variables
}
```

At the moment, we only have one such operation, `GetWeight`, but we could add more in the future. We can then modify our `SumWeights` function to take an `IListOperations`:

```csharp
static int SumWeights(
    IList<int> ints,
    IList<string> strs,
    IListOperations listOps)
    => listOps.GetWeight(ints) + listOps.GetWeight(strs);
```

This technique is a bit more verbose than a plain function, but it effectively supports universally quantified function types. (Shout out to @costinmanda for  digging into this problem in the comments!)

# Deserialization challenge

Now let's switch to a different, more unusual, problem. Imagine that we have a file that contains a list of serialized objects, all of the same type. For example, we might store a list of circles like this:

```
MyNamespace.Shapes.Circle
Origin=(3,4), Radius=5
Origin=(-2,3), Radius=7
...
```

And we might store rectangles like this:

```
MyNamespace.Shapes.Rectangle
TopLeft=(0,3), BottomRight=(3,0)
TopLeft=(1,1), BottomRight=(4,-3)
...
```

The file format itself doesn't really matter, so don't get hung up on why it's not CSV, JSON, or XML. What's important is that we can use the format to store a list of values of any relevant type.[^1]

How would you design an API to deserialize the contents of such a file? You might start with something like this:

```csharp
static IList<T> DeserializeList<T>(string path)
{
   // implementation
}

var circles = DeserializeList<Circle>("Circles.txt);
var rectangles = DeserializeList<Rectangle>("Rectangles.txt");
```

This works great, but only if you know the type contained in each file ahead of time. What if you need to be able to deserialize an arbitrary file without knowing the type of objects it contains at compile-time?

```csharp
var values = DeserializeList<???>("Arbitrary.txt");
```

We could potentially use `obj` as the type variable, so that `values` is of type `IList<obj>`:

```csharp
IList<obj> values = DeserializeList<obj>("Arbitrary.txt");
```

The problem with this approach is that an `IList<obj>` (or a non-generic `IList`) could contain a mixture of different types of objects. We don't want to lose the fact that all the values in a given file are in fact of the same type. Is there a way to represent this in C#?

# Existentially quantified types

Ideally, we'd want to write the signature of `DeserializeList` like this:

```csharp
static ∃T.IList<T> DeserializeList(string path)   // not legal C#
{
   // implementation
}
```

We've introduced `∃T.`, which means "there exists a type `T`", so `∃T.IList<T>` is a generic list containing items of some unspecified type. We call `∃T.IList<T>` an *existentially quantified type*. Note that we no longer pass a type parameter to `DeserializeList` at all, since there's no way to know the actual type that `T` represents at compile-time.

Obviously, existential types are not directly supported by C#. But is there a way to emulate them using universal types instead? The answer is yes, but the solution is not at all obvious. We'll cover it next time.

[^1]: Note that the first line of the file contains the name of the stored type. We can use this metadata to dynamically instantiate the type at runtime (via reflection or some other mechanism).