loading...

Existentially quantified types in C# - Part 2

shimmer profile image Brian Berns ・3 min read

As we discussed last time, an existentially quantified type is one that contains a hidden implementation type that is not available to the external world at compile-time.

C# doesn't support existential types directly, but we can emulate them using generics. For the purposes of this article, I'm going to call such a type a "carton", because it contains a type that can't be seen from the outside.1 So for example, a list carton is a list of items of an unknown type. How do we implement and use this carton type?

List operations

Let's start by defining an interface that describes a single operation on an IList<T>:

interface IListOperation<TReturn>
{
    TReturn ApplyTo<TItem>(IList<TItem> items);
}

Note that this interface is generic in the type returned by the operation. So, for example, an IListOperation<string> is a list operation that returns a string. The interface contains a single method, which applies the operation to any given generic list.

Here are two example list operations that implement this interface - one that returns the number of items in a list, and another that returns the runtime type of the items in a list:

class GetCount : IListOperation<int>
{
    public int ApplyTo<TItem>(IList<TItem> items)
        => items.Count;
}

class GetItemType : IListOperation<Type>
{
    public Type ApplyTo<TItem>(IList<TItem> items)
        => typeof(TItem);
}

static IListOperation<int> getCount = new GetCount();
static IListOperation<Type> getItemType = new GetItemType();

We've also created singleton instances of each class - getCount and getItemType.

List cartons

Now that we've defined operations on a list, we can define the list carton interface itself:

interface IListCarton
{
    TReturn ApplyOp<TReturn>(IListOperation<TReturn> listOp);
}

This interface is all that's exposed to the outside world about a list carton. Note that it follows the same pattern we saw previously when emulating first-class polymorphism: The interface itself is not generic, but contains a generic method that applies the given list operation to the carton's contents.

We can define a pair of small utility classes that make it easy to implement this interface:

class ListCartonImpl<TItem> : IListCarton
{
    public ListCartonImpl(IList<TItem> items)
    {
        _items = items;
    }
    private IList<TItem> _items;

    public TReturn ApplyOp<TReturn>(IListOperation<TReturn> listOp)
        => listOp.ApplyTo(_items);
}

static class ListCartonImpl
{
    public static IListCarton Create<TItem>(IList<TItem> items)
        => new ListCartonImpl<TItem>(items);
}

The key here is that ListCartonImpl<TItem> holds the actual list of items without exposing their type, TItem.

Using cartons

We're finally ready to take our faux-existential carton type out for a test drive. Creating cartons is easy:

var intCarton = ListCartonImpl.Create(new[] { 1, 2, 3 });
var strCarton = ListCartonImpl.Create(new[] { "moo", "baa" });

The cool thing here is that intCarton and strCarton have exactly the same type, IListCarton, even though one contains integers and the other contains strings. Consumers can rely on the fact that all items in a given list carton will have the same type without having to use runtime tricks like reflection or casting. It's all totally type-safe.

We can test these cartons as follows:

void Test(IListCarton listCarton)
{
    var count = listCarton.ApplyOp(getCount);
    Console.WriteLine(count);
    var type = listCarton.ApplyOp(getItemType);
    Console.WriteLine(type);
}
Test(intCarton);
Test(strCarton);

// output:
// 3
// System.Int32
// 2
// System.String

  1. The folks at G-Research who invented this technique call it a "crate", but I'm avoiding that term because it's already associated with another concept in the Rust world. I've also renamed other terms in their version, but the overall concept and credit is all theirs. 

Discussion

pic
Editor guide
Collapse
jwp profile image
John Peters

Polymorphic in that each item in list can be of any type right? Not polymorphic in that each list item can have multiple types or can it?

Collapse
shimmer profile image
Brian Berns Author

A list "carton" is a lot like an IList<T>. Each carton contains only one type of item. You can create a carton of ints or a carton of strings, and you can ensure that ints and strings aren’t mixed together in a single carton.

The important difference between an IList<T> and an IListCarton is that a carton of ints and a carton of strings have exactly the same type (IListCarton), but IList<int> isn't the same type as IList<string>.