Universally quantified types in C#
Tags: csharp, dotnet, functional
Published: 2020-03-14 03:13:52

# Generic types

Generic types in C# are universally quantified. That means, for example, that `List<T>` can contain elements of type `T` **for any type `T`**. To make the universal quantification explicit, we could imagine defining this type as:

``` csharp
public class ∀T.List<T> : IList<T>, ...   // not legal C#
{
   ...
}
```

C# leaves out the `∀T.` part (which means "for all `T`"), but it's implied.

You can think of a universally quantified type such as `List<T>` as a type-level function that takes a type as input (e.g. `int`) and returns a type as output (e.g. `List<int>`). `T` is called a "type variable", since it represents an arbitrary type.

# Parametric polymorphism

Generic types in C# are an example of what functional programming calls *parametric polymorphism*. Interestingly, C# generics implement *let-polymorphism*, which is somewhat more limited than full-blown *first-class polymorphism*.

Imagine that we're implementing an algorithm that has to work with generic lists. We need to be able to compute the "weight" of such a list, where the weight is an integer that is calculated somehow from a list. There might be multiple different ways of calculating a list's weight, so we have to be prepared to work with any of them. In particular, our job is to implement the following function:

```csharp
// fix this so it compiles and runs successfully
static int SumWeights(
    IList<int> ints,
    IList<string> strs,
    /*some type*/ getWeight)
    => getWeight(ints) + getWeight(strs);
```

As you can see, this function is passed two lists and has to sum their weights, as calculated by the given `getWeight` function. Our only problem is that we have to specify a type for `getWeight`. Since it's a function that converts a list to an integer, we can try to define the type as `Func<IList<T>, int>`:

```csharp
static int SumWeights(   // compiler error
    IList<int> ints,
    IList<string> strs,
    Func<IList<T>, int> getWeight)
    => getWeight(ints) + getWeight(strs);
```

The compiler doesn't accept this, though, because type variable `T` isn't defined anywhere. That should be easy enough to fix, right? We just have to declare `T` next to the `SumWeights` name itself:

```csharp
static int SumWeights<T>(   // compiler error
    IList<int> ints,
    IList<string> strs,
    Func<IList<T>, int> getWeight)
    => getWeight(ints) + getWeight(strs);
```

But that doesn't work either! The compiler says it can't convert an `IList<int>` or an `IList<string>` to an `IList<T>`. This makes sense, though, because by changing `SumWeights` to `SumWeights<T>` we made it generic, and the type represented by `T` is now determined by the caller of the function. The compiler is telling us that we can't assume that `T` is either `int` or `string` (and it's certainly not both at once).

What's going on here? The problem is that we want to control the scope of the type variable `T` so that it applies only to `getWeight`, not to the entire `SumWeights` function. Ideally, we'd like to write the type of `getWeight` like this:

```csharp
static int SumWeights(   // compiler error
    IList<int> ints,
    IList<string> strs,
    ∀T.Func<IList<T>, int> getWeight)
    => getWeight(ints) + getWeight(strs);
```

We've added `∀T.` here to declare the type variable `T` and show the compiler that its scope should be limited to type of `getWeight`. Of course, however, this isn't legal C#.

What's the best way to work around this limitation of generic types in C#? How would you implement the `SumWeights` function so it compiles and successfully adds the weights of the two given lists, using a function supplied by the caller to determine the weight of any given generic list? If you have an idea, suggest it in the comments!

*Credit for this idea goes to [Nicholas Cowle](https://github.com/nickcowle/Talks/blob/master/Existentials%20-%20Playing%20Hide%20and%20Seek%20With%20Your%20Types.pdf).*