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.
Top comments (12)
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:
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:
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:
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.
Thanks for your response. Can you make it work with a generic
getWeight
(i.e. one that takes anIList<T>
) and without using reflection? It can be done!Hmm... there are multiple ways to do it. I don't like any of them. This might work:
You’re on the right track with your idea to insert something that prevents the generic-ness of
getWeight
from bubbling up toSumWeights
. However, it can be done safely, without going around the compiler’s type checker viadynamic
.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.
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.
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!
Why would you try to introduce another problem and pull code from a different domain?
What if there were multiple different versions of
getWeight
, and you wanted toSumWeights
to work with any of them? You'd have to pass it in somehow as an argument, right?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 yourFunc<IList<>, int> getWeight()
method where he needs to additionally implement new case/switch to handle float sums.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
).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.
One of the requirements is that you have to pass a generic
getWeight
toSumWeights
somehow. Imagine that there are multiple different implementations ofgetWeight
that all have the same type signature. How do you tellSumWeights
which version to use?