Higher Kinded Types in C# Part 1 — Introduction

This is the first part of the HKT series. For your convenience you can find other parts using the links below:
Part 1 — Introduction
Part 2 — Homogenous invoice
Part 3 — Heterogenous invoice

Today we will play with higher kinded types in C#. If you have no idea what’s that, you can read about them at:
https://robkuz.github.io/Higher-kinded-types-in-fsharp-Intro-Part-I/
https://medium.com/@JosephJnk/what-is-higher-kinded-polymorphism-6fb2bff183f9
http://ocamllabs.io/higher/lightweight-higher-kinded-polymorphism.pdf

They are not available in .NET yet, there are proposals:
https://github.com/fsharp/fslang-suggestions/issues/175
https://github.com/dotnet/csharplang/issues/339

I am not going to show “best” implementation. Instead, I will just show possible approaches (mostly incorrect) to see how we can emulate higher kinded types (HKT).

Let’s start with the following code:

public class Invoice<T>
{
	public List<T> Items { get; set; }
}

public interface ItemStatus<T>
{
}

public class Invoice<T>

{

public List<T> Items { get; set; }

}

public interface ItemStatus<T>

{

}

We have an invoice with list of items. Each item is in some status. Let’s add some of them:

public class Started<T> : ItemStatus<T>
{
	public T Value { get; set; }
}

public class Finished<T> : ItemStatus<T>
{
	public T Value { get; set; }
}

public class Started<T> : ItemStatus<T>

{

public T Value { get; set; }

}

public class Finished<T> : ItemStatus<T>

{

public T Value { get; set; }

}

Simple enough. Now let’s create instance:

Invoice<Started<string>> startedItems = new Invoice<Started<string>>() { Items = new List<Started<string>>() { new Started<string> { Value = "Tadam!" } } };

1	Invoice<Started<string>> startedItems = new Invoice<Started<string>>() { Items = new List<Started<string>>() { new Started<string> { Value = "Tadam!" } } };

So we have invoice of started items, each of which is string. Let’s say, that we want to process all items:

public static Invoice<U> Process<T, U>(Invoice<T> invoice, Func<T, U> lambda)
{
	return new Invoice<U> { Items = invoice.Items.Select(i => lambda(i)).ToList() };
}

public static Invoice<U> Process<T, U>(Invoice<T> invoice, Func<T, U> lambda)

{

return new Invoice<U> { Items = invoice.Items.Select(i => lambda(i)).ToList() };

}

We finish the item in this way:

public static Finished<T> Finish<T>(Started<T> started)
{
	return new Finished<T> { Value = started.Value };
}

public static Finished<T> Finish<T>(Started<T> started)

{

return new Finished<T> { Value = started.Value };

}

We imagine there could be some more logic, obviously. So let’s run it:

Invoice<Finished<string>> finishedItems = Process<Started<string>, Finished<string>>(startedItems, Finish);
foreach (var item in finishedItems.Items)
{
	Console.WriteLine(item.Value);
}

Invoice<Finished<string>> finishedItems = Process<Started<string>, Finished<string>>(startedItems, Finish);

foreach (var item in finishedItems.Items)

{

Console.WriteLine(item.Value);

}

And we can see it works nice.

Are there any problems with this approach? Currently our invoice has strings only. What if we’d like to have different item types? Let’s say we want to have one string and one integer:

public class Invoice<T, U>
{
	public T Item1 { get; set; }
	public U Item2 { get; set; }
}

public class Invoice<T, U>

{

public T Item1 { get; set; }

public U Item2 { get; set; }

}

Now we initialize it with Invoice< Started< string>, Started< int>> and we are done. That’s terrible (imagine how much changes you’d need to make when adding new field). What we actually need is something like:

public class Invoice<T>
{
	public T<string> Item1 { get; set; }
	public T<int> Item2 { get; set; }
}

public class Invoice<T>

{

public T<string> Item1 { get; set; }

public T<int> Item2 { get; set; }

}

And this requires a higher kinded type. We cannot say T< string> in .NET.

So what can we do about it?

For now, let’s get back to invoice of strings and see if we can make it more generic:

Let’s introduce this type:

public class Brand<T, A>
{
}

public class Brand<T, A>

{

}

So instead of saying T< string> we will say Brand< T, string>. This way we flatten the generic type and use normal types, not higher ones. We need some marker types:

public class Started
{
}

public class Finished
{
}

public class Started

{

}

public class Finished

{

}

And now comes the invoice:

Invoice<Brand<Started, string>> startedItemsBrand = new Invoice<Brand<Started, string>>() { Items = new List<Brand<Started, string>>() { ... } };

1	Invoice<Brand<Started, string>> startedItemsBrand = new Invoice<Brand<Started, string>>() { Items = new List<Brand<Started, string>>() { ... } };

And then we process it in this way:

public static Invoice<Brand<U, string>> ProcessBrand<T, U>(Invoice<Brand<T, string>> invoice, Func<Brand<T, string>, Brand<U, string>> lambda)
{
	return new Invoice<Brand<U, string>> { Items = invoice.Items.Select(i => lambda(i)).ToList() };
}

public static Invoice<Brand<U, string>> ProcessBrand<T, U>(Invoice<Brand<T, string>> invoice, Func<Brand<T, string>, Brand<U, string>> lambda)

{

return new Invoice<Brand<U, string>> { Items = invoice.Items.Select(i => lambda(i)).ToList() };

}

Looks good. So now we can go with these flattened types. In next part we will see how to avoid Brand type just a little.