I need to create a generic tree, where children nodes can have different types.
class Node<T>
{
public T Value { get; }
public Node<?>[] Children { get; }
public Node(T value, Node<?>[] children)
{
Value = value;
Children = children;
}
}
And a simple depth calculator.
public static int Depth(Node<?> node) =>
1 + node.Children.Select(Depth)
.DefaultIfEmpty().Max();
But what can I put instead of wildcard '?' in C# ?
It cannot be 'object' because I want to restrict children of the same parent to have the same type.
It cannot be 'T' or 'T2' because different nested levels may have different types.
Type information is not used in Depth method, so I can use existential types here. But, unfortunately, C# doesn't support them.
This answer on StackOverflow suggested a hint.
∃'x.T<'x> ≡ ∀'z.(∀'x.T<'x> -> 'z) -> 'z
I can simulate existential type using two universal types. They both hide children type from the parent class.
interface IExistentialList
{
TRet Apply<TRet>(IExistentialFunc<TRet> a);
}
interface IExistentialFunc<TRet>
{
TRet Apply<T>(Node<T>[] a);
}
Children's type will be stored in implementation class.
class SpecificList<T> : IExistentialList
{
private Node<T>[] nodes;
public SpecificList(Node<T>[] nodes)
{
this.nodes = nodes;
}
public TRet Apply<TRet>(IExistentialFunc<TRet> a) => a.Apply(nodes);
}
Tree will become.
class Node<T>
{
public T Value { get; }
public IExistentialList Children { get; }
public Node(T value, IExistentialList children)
{
Value = value;
Children = children;
}
}
Depth function will become a class.
class DepthFunc : IExistentialFunc<int>
{
public static int Invoke<T>(Node<T> s) =>
new DepthFunc().Run(s);
private int Run<T>(Node<T> s) =>
1 + s.Children.Apply(this);
public int Apply<T>(Node<T>[] list) =>
list.Select(Run).DefaultIfEmpty(0).Max();
}
I can use it easily with some helper functions.
public static Node<TP> Create<TP, TC>(TP value, params Node<TC>[] array) =>
new Node<TP>(value, new SpecificList<TC>(array));
public static Node<TP> Create<TP>(TP value) =>
new Node<TP>(value, new SpecificList<object>(new Node<object>[0]));
public static void Main()
{
var tree = Create(1,
Create("test1", Create(10.5f)),
Create("test2"));
Console.WriteLine(DepthFunc.Invoke(tree));
}
