Universally quantified types in C#

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.

Comments

[Costin Manda]

Your problem is interesting. It feels like it should work, but it doesn't.
The question is really, why can't I convert IList<int> to IList<T>? Or IList<object> for that matter, since int is an object. Let's assume we could:

var ints = new List<int> { 1,2,3 };
var objs = (IList<object>)ints;

Only now I should be able to do objs.Add(new object()), and that clearly is not the case.

For your specific problem, you don't actually use the type of the list in any way, so you need to use a base type that is not generic, like System.Collections.IList:

        private static int SumWeights(
            IList<int> ints, 
            IList<string> strs, 
            Func<IList, int> getWeight) 
            => getWeight((IList)ints) + getWeight((IList)strs);

And I know your objection would be that you didn't mean specifically IList<T>, but anything, which might not have a non generic base class. Perhaps the feature in C# that you are looking for is something like this:

        private static int SumWeights(
            IList<int> ints, 
            IList<string> strs, 
            Func<IList<>, int> getWeight) 
            => getWeight(ints) + getWeight(strs);

But that's illegal in C#. A working solution could be using Func<object,Type,int> and then you would call it like getWeight(ints,typeof(IList<>)), which is legal, only now you have to do a lot of reflection in getWeight.

[Brian Berns]

Thanks for your response. Can you make it work with a generic getWeight (i.e. one that takes an IList<T>) and without using reflection? It can be done!

[Costin Manda]

Hmm... there are multiple ways to do it. I don't like any of them. This might work:

private static int SumWeights(
            IList<int> ints, 
            IList<string> strs, 
            Func<dynamic,int> getWeight) 
            => getWeight(ints) + getWeight(strs);
...
Console.WriteLine(SumWeights(ints, strs, x=>getWeight1(x)));

[Brian Berns]

You’re on the right track with your idea to insert something that prevents the generic-ness of getWeight from bubbling up to SumWeights. However, it can be done safely, without going around the compiler’s type checker via dynamic.

[Costin Manda]

You can't pass a generic function as a parameter without having your own function be generic. Therefore you need to encapsulate it. Like in an interface. This would be the best design for your problem.

    interface IWeighter
    {
        int getWeight<T>(IList<T> list);
    }

But you want to pass a function as a parameter, so probably this ain't it. I have the feeling that whatever you're proposing will not sit well with me.

[Brian Berns]

You got it. That interface is exactly what I'd suggest. You're still passing in the function, just with one level of indirection. It's a bit more verbose, but not too bad, I think. Nice work!

[Slavius]

Why would you try to introduce another problem and pull code from a different domain?

// getWeight() is a method specific to the Interface IList<T>
static int SumWeights(
    IList<int> ints,
    IList<string> strs)
    => ints.getWeight() + strs.getWeight();

[Brian Berns]

What if there were multiple different versions of getWeight, and you wanted to SumWeights to work with any of them? You'd have to pass it in somehow as an argument, right?

[Slavius]

Aren't you contradicting yourself? Shouldn't pure function always return the same result with the same input? What exactly you mean by "multiple different getWeight() functions"? Each domain implements only one existing version from the Interface. There can be differences but only in input parameters to the getWeight() method which are handled by the compiler inference.

You said you need to sum the weights. While it is possible to sum int and float by doing implicit conversion, there cannot exist implementation of an interface method with different output type.

While what you propose introduces domain modelling problem. Imagine a new developer tasked to implement IList<float>. When he's finished implementing the interface your code is still broken because he has no idea about your Func<IList<>, int> getWeight() method where he needs to additionally implement new case/switch to handle float sums.

[Brian Berns]

I think you're making this more complex than it needs to be. I'm just trying to create a scenario where you're passing a generic function (getWeight) to a non-generic method (SumWeights).

[Slavius]

Are you talking about IoC / DI? ;)

Edit: Now I remember! Your solution reminds me of Service locator pattern, which is BTW an anti-pattern. That's why I found it immediately wrong.

[Brian Berns]

One of the requirements is that you have to pass a generic getWeight to SumWeights somehow. Imagine that there are multiple different implementations of getWeight that all have the same type signature. How do you tell SumWeights which version to use?