This post is the beginning of a series in which we will look at generics more closely, we will consider their implementation details across various languages, and we will explore their potential in solving problems we have today (with static analysis in mind).

As usual, we will use C# as for our examples because its generics syntax will be self-explanatory to developers familiar with C++, Java, Rust, etc. Also, for the purposes of this post we will use the terms “function” and “method” interchangeably.

Let’s examine a simple generic method definition:

1
2
3
4

T M<T>(T x)
{
    return x;
}

Since it’s a single-expression function, we can exploit C# syntactic sugar to write it out like this:

1

T M<T>(T x) => x;

In any case, if you understand what this code does, you may describe M as a generic method that takes an object of type T (where T can be any type) and returns that same object — in other words, it’s a (generic) identity function.

And that would be a fine response, but in this post we will try describing generics in a different manner. Before we do that, however, let’s take a small detour.

Currying

In lambda calculus, the concept of currying allows us to transform a function of any number of parameters to an equivalent function of just one parameter.

For example, a function that takes two parameters is (from a certain point of view) equivalent to a function that takes one parameter and returns another function that takes the other parameter (and vice versa).

Let’s see this in code. Here’s a C# function that takes two integers and returns their sum:

1
2

Func<int, int, int> uncurried = (x, y) => x + y;
int sum = uncurried(1, 3);

For non-C# readers, Func<A, B, C> is the type of a function that takes two parameters of types A and B respectively, and returns a value of type C. Thus, the C# type Func<A, B, C> represents a function that could be notated as $ (A, B) \rightarrow C $.

Now how do we apply currying to the above function? By turning it into a function that takes one integer and produces a function that takes another integer and returns the sum of those aforementioned integers:

1
2

Func<int, Func<int, int>> curried = x => y => x + y;
int sum = curry(1)(3);

Here, Func<A, B> is the type for functions of the form $A \rightarrow B$ and it follows that Func<A, Func<B, C>> is the type for functions of the form $ A \rightarrow (B \rightarrow C) $ or, without the parentheses, $ A \rightarrow B \rightarrow C $.

In this example, we went from having one function that takes two integers to having a function that takes an integer and creates a function. Obviously, these two approaches aren’t exactly the same thing in most languages — but the point of currying is that they are two different ways of expressing the same thing, in the sense that passing the same information will eventually get you to the same final result.

In general, currying allows us to reason about single-parameter functions and then generalize our conclusions to functions that can have any number of parameters. Essentially, it allows us to mentally break down the application of multiple arguments into a number of distinct steps — an approach that we will use immediately.

Partial application of different kinds of arguments

Let’s go back to our initial snippet:

1

T M<T>(T x) => x;

We know that there are two sets of things called “parameters” here:

  • One set of parameters are the generic type parameters, listed in angle brackets. In this example there is only one type parameter, identified as T.
  • The other set of parameters are the formal parameters, listed in parentheses. Again, in this example there is only one formal parameter, identified as x (of type T).

If we add them together, we could say that this method takes two parameters in total. They are different kinds of parameters, but they are still parameters of this function in one way or another.

Under that light, consider the usage of this method:

1

M<int>(3);

You could say that it’s syntactically reminiscent of:

1

curry(1)(3);

Better yet, you could say that M is some kind of “super-function” (a fictitious term I’m coining right now) that takes one parameter (a type) in angle brackets and returns some kind of function.

To demonstrate that this view is reasonable, I’m going to actually call the “super-function” M with just one argument in angle brackets — that argument will be the type int. Here we go:

1

Func<int, int> f = M<int>;

This is valid C#, showing that a call to the “super-function” M with the argument int does indeed return a regular function that takes an int and returns an int. That regular function can subsequently be called to produce a result:

1

int r = f(3);

Consider what we demonstrated here: that a generic method is conceptually just a “super-function” that takes one or more types and returns a regular function (and the regular function is usually parameterized by those types somehow).

In other words, a generic method definition is a “super-function” from types to functions.

Very similarly, here is a generic type definition:

1
2
3
4

class C<T>
{
    public T Value;
}

Again, you could say that G is not a type — it’s actually yet another ”super-function” with a single type parameter. Except this time, when you apply a type argument to that “super-function”, you get a type.

Therefore, a generic type definition is a “super-function” from types to types.

What C# programmers tend to call generic type definitions, Haskell programmers call type constructors — special functions whose purpose is to take a type and construct a type. (Contrast that with regular functions, which are called value constructors.)

Next

That was simple enough. In a future post, we will continue thinking about generics as “super-functions” in order to examine some other potential properties, like alternative kinds of parameters and generic variance.