This is the third part of the Higher Kinded Types in C# series. For your convenience you can find other parts in the table of contents in Part 1 — Introduction

This time we start with this invoice:

public class HeterogenousInvoice<T> where T : BrandProvider, new()
{
	public Brand<T, string> Item1 { get; set; }
	public Brand<T, int> Item2 { get; set; }
}

Obviously, this breaks things now. We need to add these two things to Brand:

public Brand<T, object> ToObject() => new Brand<T, object> { Target = this.Target };
public Brand<T, V> FromObject<V>() => new Brand<T, V> { Target = this.Target };

Since we cannot use covariance and contravariance easily, we need to do upcasting and downcasting in generics “the hard way”.

We create invoice this way:

HeterogenousInvoice<Started> startedHeterogenous = new HeterogenousInvoice<Started>()
{
	Item1 = Brand<Started, string>.FromHKT(new Started<string> { Value = "String" }),
	Item2 = Brand<Started, int>.FromHKT(new Started<int> { Value = 123 })
};

Okay, now how to process it? We’d like to have one function translating Started< T> into Finished< T> and we already have it, it’s called Finish. How to reuse it?

We cannot use it directly as it works on Started< T> type. But we cannot use FinishBrand method either because then compiler will go crazy as it cannot handle one lambda for Started< string> and Started< int>. What can we do? Upcasting and downcasting:

public static Func<Brand<T, V>, Brand<U, V>> Rebind<T, U, V>(Func<Brand<T, object>, Brand<U, object>> lambda) where T : BrandProvider, new() where U : BrandProvider, new()
{
	return (Brand<T, V> v) => (lambda(v.ToObject())).FromObject<V>();
}

So we accept lambda working on the base type object. The trick is, we can transform original lambda in this way:

public static HeterogenousInvoice<U> ProcessHeterogenous<T, U>(HeterogenousInvoice<T> invoice, Func<Brand<T, object>, Brand<U, object>> lambda) where T : BrandProvider, new() where U : BrandProvider, new()
{
	return new HeterogenousInvoice<U>
	{
		Item1 = Rebind<T, U, string>(lambda)(invoice.Item1),
		Item2 = Rebind<T, U, int>(lambda)(invoice.Item2)
	};
}

So we just magically transform lambdas using upcasting and downcasting.

Let’s see this in action:

HeterogenousInvoice<Started> startedHeterogenous = new HeterogenousInvoice<Started>()
{
	Item1 = Brand<Started, string>.FromHKT(new Started<string> { Value = "String" }),
	Item2 = Brand<Started, int>.FromHKT(new Started<int> { Value = 123 })
};
HeterogenousInvoice<Finished> finishedHeterogenous = ProcessHeterogenous(startedHeterogenous, FinishBrand);
Console.WriteLine(finishedHeterogenous.Item1.GetHKT().Value);
Console.WriteLine(finishedHeterogenous.Item2.GetHKT().Value);

This is the second part of the Higher Kinded Types in C# series. For your convenience you can find other parts in the table of contents in Part 1 — Introduction

So now we can use invoice with items as Brand< Started, string>. However, what we really want to use is Started< string>. How can we do that?

We need to use some magic to seamlessly translate Started< string> into Brand< Started, string>. Notice that there are two different Started types here: one is generic, one is not. And they are completely unrelated when it comes to class hierarchy.

Let’s start with this:

public class Brand<T, A> where T : BrandProvider, new()
{
	public object Target { get; set; }
	public dynamic GetHKT() => new T().GetReal<A>(Target);
	public static Brand<T, A> FromHKT(object target) => new Brand<T, A> { Target = target };
}

So we store the target of this object (which is our Started< string> instance). We also have some helper methods to translate to and from higher kinded type.

We need this:

public interface BrandProvider
{
	dynamic GetReal<A>(object target);
}

So we have some provider of real object casted to correct type. We go with dynamic just to make it simpler when it comes to type casting since .NET doesn’t support overriding method with covariant return type so we’d need to cast it on the caller side (which we want to avoid).

Now, markers:

public class Started : BrandProvider
{
	public dynamic GetReal<U>(object target) => (Started<U>)(target);
}

public class Finished : BrandProvider
{
	public dynamic GetReal<U>(object target) => (Finished<U>)(target);
}

So we just cast the type correctly.

Now we process invoice 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) where T : BrandProvider, new() where U : BrandProvider, new()
{
	return new Invoice<Brand<U, string>> { Items = invoice.Items.Select(i => lambda(i)).ToList() };
}

To finish an item we do this:

public static Brand<Finished, T> FinishBrand<T>(Brand<Started, T> started)
{
	return Brand<Finished, T>.FromHKT(Finish(started.GetHKT()));
}

So we reuse Finish method which we used last time. That method worked on normal generic typ, now we reuse it to work on our flattened higher kinded type.

Let’s now create invoice and run the magic:

Invoice<Brand<Started, string>> startedItemsBrand = new Invoice<Brand<Started, string>>() { Items = new List<Brand<Started, string>>() { Brand<Started, string>.FromHKT(new Started<string> { Value = "Tadam!" }) } };
Invoice<Brand<Finished, string>> finishedItemsBrand = ProcessBrand<Started, Finished>(startedItemsBrand, FinishBrand);
foreach (var item in finishedItemsBrand.Items)
{
	Console.WriteLine(item.GetHKT().Value);
}

Crucial parts here are:

Brand<Started, string>.FromHKT(new Started<string> { Value = "Tadam!" })

and

item.GetHKT().Value

This way we can transform items from one to the other.

This handles homogenous items. Next time we will see how to have items of different types.

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>
{
}

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; }
}

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!" } } };

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() };
}

We finish the item in this way:

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);
}

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; }
}

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; }
}

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>
{
}

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
{
}

And now comes the invoice:

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() };
}

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.