An introduction to parameterised types

This article is about parameterised types, which are also known as generics or parametric polymorphism.  I first came across them in the functional programming language ML, but they have spread beyond the functional programming world, to languages like Java, C#, and TypeScript.

What are parameterised types?

Parameterised types are, as the name suggests, types that take one or more parameters.  It might not be obvious at first why you’d want to do this, particularly as there are many types such as int, string, boolean etc. that don’t take parameters and are nonetheless useful.

Parameterised types let you define a type in general, abstract terms, and then to use it e.g. as the type of a variable, you often (but not always) make it specific and concrete.  So, a parameterised type is something like List<T>, where T is a parameter.  Unlike the parameters usually passed to methods and functions, T is always a type e.g. int or string, and not a value such as 42.  You might then have a variable whose type is e.g. List<int>.

When you define a method that takes normal parameters, you don’t know what values those parameters will have when other code uses this method. You define your method such that it will exclude 0 or more values (via validating its inputs, throwing exceptions etc.), and then cope with all other possible values. It’s similar when you define parameterised types – you don’t know when you define it what values will be passed in when other code uses the type. If there are certain values that don’t make sense, you need to exclude these (see below).

There’s another similarity with methods (well, methods with no side effects). I can write code that calls a method on two subsequent lines, passing it different values, and the two calls of that method are independent. A parameterised type is like that – I can have two variables on neighbouring lines, where one is e.g. List<int> and the other is List<string>.

Why use parameterised types?

The reason why you might want to define a parameterised type is when there are aspects of its behaviour that don’t worry about the specifics of types.  For instance, if I said that there was a list of things, you might expect that this list could:

• Tell you how many things were in the list
• Accept a new thing
• Let you remove one or more things from the list
• Tell you if a particular thing was in the list
• Etc.

This description makes sense even though I haven’t told you what kind of things are in the list.  Are they ints, strings or something else?  In some ways it doesn’t matter.  In C#, there are further statements you can make, such as: all the things in a given list will be the same type as each other, i.e. they’ll all be ints or they’ll all be booleans etc.  Again, it doesn’t matter which specific type it is, that statement will always be true.

The alternative to parameterised types is to define lots of very similar types, e.g. StringList, IntList, BoolList etc.  Each time you wanted a list of a new kind of thing you would need to define it from scratch.  Its definition would look a lot like the definitions for the other kinds of list, other than the specific type that’s added, tested for etc.

A table to show similar and different

The columns heading in this table are all parameterised types, and the row headings are all types that you could use to produce concrete types in the body of the table.

The cells in a given column all have something to do with each other, and the cells in a given row all have something to do with each other.  A variable of any of the types in the first column would be an object that, as described above, could accept new things, say how many things it contained, say if it contained a given thing etc, i.e. they’re all list-y.  A variable of any of the types in the last column would be an object that could tell you if it’s empty, accept a new thing, and remove the last thing added, i.e. they’re all stack-y.

Similarly, I could have a variable of any of the types in the first row, take a few things from it and then sum those things up, or count how many were odd, i.e. they’re all int-y.  I could have a variable of any of the types in the second row, take a few things from it and calculate the average length of them, or count how many contained a particular substring, i.e. they’re all string-y.

List<int> and List<string> are similar but different.  Likewise, List<int> and Stack<int> are similar but different.  Parameterised types are often a convenient way of representing these relationships.

Note that all the parameterised types in this table are collections of some sort – they hold onto data for you, to return it later.  This isn’t the only use of parameterised types, but it’s one of the simplest to get your head around.

Getting more complicated

There are a few ways that parameterised types can get more complicated than they have been so far.

The first way is to accept more than one type parameter.  An example is Dictionary<T,U>, which a way of storing key/value pairs where the key has type T and the value has type U.  T and U can be the same as each other, or they can be different.  As before, it doesn’t really matter what T and U are – you can still define behaviour that you expect the dictionary to have.  This is things like:

• Adding a new entry
• Looking up an existing entry
• Seeing if it contains a given key
• Giving a list of all keys

Another way to get more complicated is to use parameterised types as the values passed to other parameterised types.  An example is Dictionary<int, List<string>> – the keys for this dictionary have type int, and looking up a key will return a value that is a List<string>.  It can be a bit daunting to have lots of << and >>, but with practice they become no more daunting than nested function or method calls.

Func and Action are other examples in C# of types that can take many parameters.  A Func is a variable whose value is a function (or method), and so the parameters to Func are the types of the arguments to that method plus the type returned by the method.  E.g. Func<int, string, bool> is a variable whose value is a function that accepts int and string arguments, and returns a bool.  Actions are like Funcs, except the method in question doesn’t return anything.  So Action<int, string> is a variable whose value is a function that accepts int and string arguments (and returns nothing).

A third way to make parameterised types more complicated is to put constraints on the values you can pass to a type’s parameters.  For instance, if you were building something like Tree<T>, you need to be able to say, for a pair of values A and B, is A < B?  I.e. you need to be able to compare them.  In C# this is indicated by implementing the interface IComparable.  So you would probably want to do something like this in your definition:

public class Tree<T> where T : IComparable
{
// definition of Tree goes here
}

This is the C# syntax for saying that T must be a type that implements IComparable.

Example

In C# the standard List<T> class has, among other things, a Reverse method, but I want to pretend it doesn’t. I’ll define a simple version, and then show it being used.

public static List<T> Reverse<T> (List<T> toReverse)
{
	List<T> results = new List<T>();
	
	for(int index=toReverse.Count-1; index >= 0; index--)
	{
		results.Add(toReverse[index]);
	}
		
	return results;
}

Note that I can write this without knowing if the list being reversed is List<int>, List<string> or something else. All I need to know is that a list has a property that holds its length, and methods for accessing an element via its index and for adding a new element onto the end. Despite not knowing this, someone looking at the signature (and reading its name) knows that if I pass in a list I will get back a list of the same type (and not a list of a different type, or an integer, or one element in the list etc.).

It could be used as below. Note that in recent enough versions of C#, Reverse<int> and Reverse<string> can both be written as just Reverse as the compiler can infer what should be there.

List<string> stringList = new List<string>{"a", "b", "c"};
List<string> reversedStrings = Reverse<string>(stringList);
// reversedStrings is {"c", "b", "a"}
		
List<int> intList = new List<int>{1, 2, 3};
List<int> reversedInts = Reverse<int>(intList);
// reversedInts is {3, 2, 1}

An example using Func

In this example, I’m going to pretend that LINQ’s Select doesn’t exist, which performs the role of Map in other languages. You have a list, array etc. and you want to generate a second list or array based on it, where each element of the input array is fed through a function that will produce the corresponding element of the output array. Also, I’m going to pretend that lambda expressions (anonymous functions) don’t exist. They are shorter but don’t have explicit type information, and I think that explicit types would be helpful here.

public static List<U> Map<T,U>(List<T> inputList, Func<T,U> mapFunction)
{
	List<U> result = new List<U>();
		
	foreach(T input in inputList)
	{
		result.Add(mapFunction(input));
	}
		
	return result;
}

The output list might have the same type of elements as the input list, but it might not. That’s why there are separate type parameters for input (T) and output (U). Because they stand for types, the common convention at least in C# is to name them starting at T.

Here are two different examples of using it – the first has different types for the two lists, and the second has the same type for them.

public static int StringLength(string s) { return s.Length; }
	
public static int SquareInt(int i) { return i * i; }
	
public static void Main()
{
	List<string> stringList = new List<string>{"apple", "banana", "cherry"};
	List<int> stringLengths = Map<string, int>(stringList, StringLength);
	// stringLengths = {5, 6, 6}
		
	List<int> intList = new List<int>{1, 2, 3};
	List<int> squaredInts = Map<int, int>(intList, SquareInt);
	// squaredInts = {1, 4, 9}
}

Wrapping up

Parameterised types are a way of representing a set or family of types that are similar but different.  This is often possible when the behaviour of a type can be expressed without needing to know the specific component type, as in lists, stacks, queues etc.