Parent-Child Data Structure without an Explicit Leaf Node Class using Generics

Question

I have the following example relationship:

namespace Yesod
{
    public class Program
    {
        //
        //
        //
        public struct Particle
        {
            public byte type;
        }

        //
        //
        //
        public class Entity<T>
        {
            public Entity<Entity<T>> Parent
            { get; private set; }

            //
            //
            //
            public Entity(Entity<Entity<T>> parent)
            {
                this.Parent = parent;
            }
        }

        //
        //
        //
        public sealed class Atom : Entity<Particle>
        {
            public Atom(Entity<Atom> parent)
                : base(parent) // Compile Error.
            { }
        }

        //
        //
        //
        public sealed class Molecule : Entity<Atom>
        {
            public Molecule()
                : base(null)
            { }
        }

        static void Main(string[] args)
        {

        }
    }
}

How would I solve the following compile error that the above produces?

  Argument 1: cannot convert from 'Yesod.Program.Entity<Yesod.Program.Atom>' to 'Yesod.Program.Entity<Yesod.Program.Entity<Yesod.Program.Particle>>'

Comment Reply #1: Specifically, the code is trying to assign an object of type

Entity<Atom>

to an object of type

Entity<Entity<Particle>>

as Atom is implemented as

public sealed class Atom : Entity<Particle>

whereby

Entity<Atom>

is expected to breakdown into

Entity<Entity<Particle>>

What you want to do? you structure is wrong – Navid Rahmani Jun 13 '11 at 13:54 — Navid Rahmani, Jun 13 '11 at 13:54

Daniel Martin · Answer 1 · 2011-06-13T14:58:11.567

I don't know C#, but Java programmers occasionally slam into this issue too.

Looking around at other C# sources, I think you can do what you want (with a little loss in type safety) with:

    public class Entity<T>
    {
        public Entity<P> Parent
            where P : Entity<Entity<T>>
        { get; private set; }

        //
        //
        //
        public Entity(Entity<P> parent)
            where P : Entity<Entity<T>>
        {
            this.Parent = parent;
        }
    }

The Java answer would involve ? extends Entity<T>. The basic issue is that although Molecule is an Entity<Atom>, there's no way for the compiler to know that Molecule is also an Entity<Entity<Particle>>. After all, suppose that Entity maintained a list of children, and had the sensible addChild(T child) method on it. Then the compiler would want to ensure that you only added Atoms as children of molecules. But if Molecule is an Entity<Entity<Particle>>, then nothing would prevent you from doing:

Entity<Entity<Particle>> downcast = myMolecule;
downcast.addChild(myNonAtomParticleBasedEntity);

The proper fully type-safe solution for this pattern involves self types, which Java and C# don't have. The Java pattern of Foo<F extends Foo<F>> (and its C# equivalent) comes close, but is very slippery to work with. Barring that, declare-time variance would make this pattern cleaner.

score 0 · Accepted Answer · edited May 23 '17 at 12:20

Although the potential solution posted by Daniel Martin would never work (as admittedly warned), the explanation on why my code would too never work is 100% accurate, and it has led me to discover that C# 4.0 solves this otherwise expected functionality using its new generic covariance & contra-variance language features.

Below is the solution, for review:

namespace Yesod
{
    public class Program
    {
        //
        //
        //
        public struct Particle
        {
            public byte type;
        }

        // Fix with C# 4.0 using out keyword.
        //
        //
        public interface IEntity<out T>
        {
            IEntity<IEntity<T>> Parent
            { get; }
        }

        //
        //
        //
        public class Entity<T> : IEntity<T>
        {
            public IEntity<IEntity<T>> Parent
            { get; private set; }

            //
            //
            //
            public Entity(IEntity<IEntity<T>> parent)
            {
                this.Parent = parent;
            }
        }

        //
        //
        //
        public sealed class Atom : Entity<Particle>
        {
            public Atom(Entity<Atom> parent)
                : base(parent) // No more compile error.
            { }
        }

        //
        //
        //
        public sealed class Molecule : Entity<Atom>
        {
            public Molecule()
                : base(null)
            { }
        }

        //
        //
        //
        static void Main(string[] args)
        {
            // Now this can be done.
            Molecule water = new Molecule();
            Atom H1 = new Atom(water);
            Atom O1 = new Atom(water);
            Atom O2 = new Atom(water);
        }
    }
}

Thanks Daniel Martin. I could not 1-up you due to my current rep. score. To those wondering, the above is a silly mock up aimed to highlight obvious parent-child relationships to help those understand the question. The real-world intended use will be an advanced version that will be employed in the field of computer graphics to solve the Coherent Space Partitioning problem in a well-defined and recursive manner.

Parent-Child Data Structure without an Explicit Leaf Node Class using Generics

2 Answers2