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:

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:

// 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>:

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:

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:

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.