Discriminated Union (sum-type, co-product) from Algebraic Data Types (ADT) for C# which is memory efficient, supports one-line sub-typing

main.cs

using System;
using System.Collections.Generic;
using static System.Console;

namespace Union
{
    class Program
    {
        public static void Main()
        {
            // Unnamed union, fast declare and use
            var i = U<int, string>.Of(42);
            var s = U<int, string>.Of("heh");
            WriteLine(i); WriteLine(s);

            // You may create the case directly via constructor, helpful for cases U<A, A>, e.g. U<string, string>
            var s2 = new U<int, string>.Case1(24);
            WriteLine(s2);

            // Typed union, the type is different from U<int, string>, e.g. `s = name;` won't compile
            var name = FlagOrName.Of("Bob");
            var flag = FlagOrName.Of(false);
            WriteLine(Usage.PatternMatching(name));
            WriteLine(Usage.PatternMatching(flag));
            WriteLine(name.Map(f => "" + f, n => n));

            // Typed union with Typed cases! so you can pattern match on `case I<Name>` or `I<Flag>
            var name2 = FlagOrName2.Of(Name.Of("Alice"));
            var flag2 = FlagOrName2.Of(Flag.Of(true));
            WriteLine(Usage.PatternMatchingWithTypedCases(name2));
            WriteLine(Usage.PatternMatchingWithTypedCases(flag2));
            WriteLine(flag2.Map(f => "" + f.V, n => n.V));

            // Familiar MayBe type, defined as `sealed class Optional<T> : Union<Optional<T>, Unit, T> {}`.
            WriteLine(Some.Of(42));
            WriteLine(None.Of<int>());

            // Examples of recursive types: linked List and binary Tree, see below on how.
            WriteLine(List<int>.Empty.Push(3).Push(2).Push(1));
            WriteLine(Tree.Of(
                Tree.Of(Tree<string>.Empty, "a", Tree<string>.Empty),
                "b",
                Tree.Of(Tree<string>.Empty, "c", Tree<string>.Empty)));
        }
    }

    // One line sub-typing
    public sealed class FlagOrName : Union<FlagOrName, bool, string> { }

    // A different type!
    public sealed class Other : Union<Other, bool, string> { }

    // Typed union with a typed cases! Now you can pattern match via `I<Flag>` and `I<Name>`
    public sealed class FlagOrName2 : Union<FlagOrName2, Flag, Name> { }
    public sealed class Flag : Rec<Flag, bool> { }
    public sealed class Name : Rec<Name, string> { }

    public static class Usage
    {
        // note: Using T with constraint instead of FlagOrName.I interface improves the performace by avoiding boxing.
        public static string PatternMatching<T>(T x) where T : FlagOrName.I
        {
            switch (x)
            {
                case FlagOrName.Case1 b: return "" + b; // b.Value for the actual value
                case FlagOrName.Case2 s: return "" + s;
                default: throw new NotSupportedException();
            }
        }

        public static string PatternMatchingWithTypedCases(FlagOrName2.I x)
        {
            // Refactoring friendly Named cases, with some performance price due the boxing - likely is not important for your case, 
            // except you are designing a performance oriented data structure or being used in performance sensetive spot context.
            // The performance price may be gained back any time by switching to CaseN struct matching.
            switch (x)
            {
                case I<Flag> b: return "" + b; // b.Value.Value for the actual value
                case I<Name> s: return "" + s;
                default: throw new NotSupportedException();
            }
        }
    }

    public class Optional<T> : Union<Optional<T>, Unit, T>
    {
        // User-friendly custom Case names
        public static readonly Case1 None = Of(Unit.unit);
        public static Case2 Some(T x) => new Case2(x);
    }

    // Named facades for the cases are the best for inference and simplicity of use.
    public static class None
    {
        public static Optional<T>.Case1 Of<T>() => Optional<T>.None;
    }

    public static class Some
    {
        public static Optional<T>.Case2 Of<T>(T x) => Optional<T>.Some(x);

        // Other helpers ...
        public static Optional<R>.I Run<T, R>(this Optional<T>.I source, Func<T, R> map) =>
            source.Map< Optional<R>.I>(_ => Optional<R>.None, x => Of(map(x)));
    }

    // Enum without additional state in Union desguise. Can be pattern matched as `case I<Increment> _: ...; break;`
    public sealed class CounterMessage : Union<CounterMessage, Increment, Decrement> { }
    public struct Increment { }
    public struct Decrement { }

    // I expect it should not compile, but..
    // 
    // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    // !!! IT CRASHES VISUAL STUDIO !
    // !!!
    // !!! Crashes VS 15.7.4 and 15.6, LinqPad 5.26.01, sharplab.io
    // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    //public sealed class ListX<T> : Union<ListX<T>, Unit, (T, ListX<T>.I)> {}

    // Indeed, below line just does not compile!
    //public sealed class ListY<T> : Union<ListY<T>, Unit, ListY<T>.I> { }

    // Recursive definition with a bit of boilerplate - defining nested NonEmptyList struct.
    public sealed class List<T> : Union<List<T>, Unit, List<T>.NonEmptyList>
    {
        public static readonly Case1 Empty = Of(Unit.unit);
        public static Case2 NonEmpty(T head, I tail) => Of(new NonEmptyList(head, tail));

        // note: The Equality implementation is optional, cause recursive structures "rarely" used as key in dictionary or participate in comparison
        public readonly struct NonEmptyList
        {
            public readonly T Head;
            public readonly I Tail;
            public NonEmptyList(T head, I tail) => (Head, Tail) = (head, tail);
            public override string ToString() => Head + "::" + Tail;
        }
    }

    public static class List
    {
        public static List<T>.Case2 Push<T>(this List<T>.I list, T head) => 
            List<T>.NonEmpty(head, list);
    }

    // Less efficient, but less boilerplate recursive type - requires one heap reference per recursive type usage.
    public sealed class Tree<T> : Union<Tree<T>, Unit, Tree<T>.NonEmptyTree>
    {
        public sealed class NonEmptyTree : Rec<NonEmptyTree, (I Left, T Leaf, I Right)> { }
        public static readonly Case1 Empty = Of(Unit.unit);
    }

    public static class Tree
    {
        public static Tree<T>.I Of<T>(Tree<T>.I left, T leaf, Tree<T>.I right) =>
            Tree<T>.Of(Tree<T>.NonEmptyTree.Of((left, leaf, right)));
    }

    // Core library implementation starts here
    //----------------------------------------------------

    /// Void replacement actually usable as type argument and value, e.g. singleton empty record type, () in Haskell https://en.wikipedia.org/wiki/Unit_type
    public struct Unit
    {
        /// Single value
        public static readonly Unit unit = new Unit();
        public override string ToString() => "unit";
    }

    /// Useful for type pattern matching via `case I&lt;T&gt;: ...`
    public interface I<out T>
    {
        T V { get; }
    }

    public static class Union
    {
        /// Less strange name for `.V.V` access to the nested case value
        public static T Value<T>(this I<I<T>> i) => i.V.V;

        internal static string ToString<TName, T>(T value)
        {
            var type = typeof(TName);
            if (type == typeof(Unit)) return "(" + value + ")";
            var i = type.Name.IndexOf('`');
            if (i == -1) return type.Name + "(" + value + ")";
            return type.Name.Substring(0, i) + "(" + value + ")";
        }
    }

    public abstract class Rec<TRec, T> :
        IEquatable<Rec<TRec, T>>, I<T>
        where TRec : Rec<TRec, T>, new()
    {
        public static TRec Of(T v) => new TRec { V = v };

        public T V { get; private set; }

        public bool Equals(Rec<TRec, T> other) => other != null && EqualityComparer<T>.Default.Equals(V, other.V);
        public override bool Equals(object obj) => obj is Rec<TRec, T> c && Equals(c);
        // ReSharper disable once NonReadonlyMemberInGetHashCode
        public override int GetHashCode() => EqualityComparer<T>.Default.GetHashCode(V);
        public override string ToString() => Union.ToString<TRec, T>(V);
    }

    /// Enables one line struct subtyping. 
    /// It may be more optimal than <see cref="Rec{TRec, T}"/> but does not support recursive cases of Union
    public abstract class Case<TType, T>
    {
        public static I Of(T x) => new I(x);

        public struct I : IEquatable<I>
        {
            public T V => _v;
            public readonly T _v;
            public I(T v) { _v = v; }

            public bool Equals(I other) => EqualityComparer<T>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is I c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T>(V);
        }
    }

    public sealed class U<T1, T2> : Union<Unit, T1, T2> { }
    public abstract class Union<TType, T1, T2>
    {
        public interface I { R Map<R>(Func<T1, R> map1, Func<T2, R> map2); }

        public static Case1 Of(T1 x) => new Case1(x);
        public static Case2 Of(T2 x) => new Case2(x);

        public struct Case1 : I, IEquatable<Case1>, I<T1>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2) => map1(V);

            public T1 V => _v;
            public readonly T1 _v;
            public Case1(T1 v) { _v = v; }

            public bool Equals(Case1 other) => EqualityComparer<T1>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case1 c1 && Equals(c1);
            public override int GetHashCode() => EqualityComparer<T1>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T1>(V);
        }

        public struct Case2 : I, IEquatable<Case2>, I<T2>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2) => map2(V);

            public T2 V => _v;
            public readonly T2 _v;
            public Case2(T2 v) { _v = v; }

            public bool Equals(Case2 other) => EqualityComparer<T2>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case2 c2 && Equals(c2);
            public override int GetHashCode() => EqualityComparer<T2>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T2>(V);
        }
    }

    public sealed class U<T1, T2, T3> : Union<Unit, T1, T2, T3> { }
    public abstract class Union<TType, T1, T2, T3>
    {
        public interface I { R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3); }

        public static Case1 Of(T1 x) => new Case1(x);
        public static Case2 Of(T2 x) => new Case2(x);
        public static Case3 Of(T3 x) => new Case3(x);

        public struct Case1 : I, IEquatable<Case1>, I<T1>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3) => map1(V);

            public T1 V => _v;
            public readonly T1 _v;
            public Case1(T1 v) { _v = v; }

            public bool Equals(Case1 other) => EqualityComparer<T1>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case1 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T1>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T1>(V);
        }

        public struct Case2 : I, IEquatable<Case2>, I<T2>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3) => map2(V);

            public T2 V => _v;
            public readonly T2 _v;
            public Case2(T2 v) { _v = v; }

            public bool Equals(Case2 other) => EqualityComparer<T2>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case2 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T2>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T2>(V);
        }

        public struct Case3 : I, IEquatable<Case3>, I<T3>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3) => map3(V);

            public T3 V => _v;
            public readonly T3 _v;
            public Case3(T3 v) { _v = v; }

            public bool Equals(Case3 other) => EqualityComparer<T3>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case3 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T3>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T3>(V);
        }
    }

    public sealed class U<T1, T2, T3, T4> : Union<Unit, T1, T2, T3, T4> { }
    public abstract class Union<TType, T1, T2, T3, T4>
    {
        public interface I { R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4); }

        public static Case1 Of(T1 x) => new Case1(x);
        public static Case2 Of(T2 x) => new Case2(x);
        public static Case3 Of(T3 x) => new Case3(x);
        public static Case4 Of(T4 x) => new Case4(x);

        public struct Case1 : I, IEquatable<Case1>, I<T1>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4) => map1(V);

            public T1 V => _v;
            public readonly T1 _v;
            public Case1(T1 v) { _v = v; }

            public bool Equals(Case1 other) => EqualityComparer<T1>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case1 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T1>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T1>(V);
        }

        public struct Case2 : I, IEquatable<Case2>, I<T2>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4) => map2(V);

            public T2 V => _v;
            public readonly T2 _v;
            public Case2(T2 v) { _v = v; }

            public bool Equals(Case2 other) => EqualityComparer<T2>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case2 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T2>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T2>(V);
        }

        public struct Case3 : I, IEquatable<Case3>, I<T3>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4) => map3(V);

            public T3 V => _v;
            public readonly T3 _v;
            public Case3(T3 v) { _v = v; }

            public bool Equals(Case3 other) => EqualityComparer<T3>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case3 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T3>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T3>(V);
        }

        public struct Case4 : I, IEquatable<Case4>, I<T4>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4) => map4(V);

            public T4 V => _v;
            public readonly T4 _v;
            public Case4(T4 v) { _v = v; }

            public bool Equals(Case4 other) => EqualityComparer<T4>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case4 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T4>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T4>(V);
        }
    }

    public sealed class U<T1, T2, T3, T4, T5> : Union<Unit, T1, T2, T3, T4, T5> { }
    public abstract class Union<TType, T1, T2, T3, T4, T5>
    {
        public interface I { R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4, Func<T5, R> map5); }

        public static Case1 Of(T1 x) => new Case1(x);
        public static Case2 Of(T2 x) => new Case2(x);
        public static Case3 Of(T3 x) => new Case3(x);
        public static Case4 Of(T4 x) => new Case4(x);
        public static Case5 Of(T5 x) => new Case5(x);

        public struct Case1 : I, IEquatable<Case1>, I<T1>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4, Func<T5, R> map5) => map1(V);

            public T1 V => _v;
            public readonly T1 _v;
            public Case1(T1 v) { _v = v; }

            public bool Equals(Case1 other) => EqualityComparer<T1>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case1 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T1>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T1>(V);
        }

        public struct Case2 : I, IEquatable<Case2>, I<T2>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4, Func<T5, R> map5) => map2(V);

            public T2 V => _v;
            public readonly T2 _v;
            public Case2(T2 v) { _v = v; }

            public bool Equals(Case2 other) => EqualityComparer<T2>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case2 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T2>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T2>(V);
        }

        public struct Case3 : I, IEquatable<Case3>, I<T3>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4, Func<T5, R> map5) => map3(V);

            public T3 V => _v;
            public readonly T3 _v;
            public Case3(T3 v) { _v = v; }

            public bool Equals(Case3 other) => EqualityComparer<T3>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case3 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T3>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T3>(V);
        }

        public struct Case4 : I, IEquatable<Case4>, I<T4>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4, Func<T5, R> map5) => map4(V);

            public T4 V => _v;
            public readonly T4 _v;
            public Case4(T4 v) { _v = v; }

            public bool Equals(Case4 other) => EqualityComparer<T4>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case4 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T4>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T4>(V);
        }

        public struct Case5 : I, IEquatable<Case5>, I<T5>
        {
            public R Map<R>(Func<T1, R> map1, Func<T2, R> map2, Func<T3, R> map3, Func<T4, R> map4, Func<T5, R> map5) => map5(V);

            public T5 V => _v;
            public readonly T5 _v;
            public Case5(T5 v) { _v = v; }

            public bool Equals(Case5 other) => EqualityComparer<T5>.Default.Equals(V, other.V);
            public override bool Equals(object obj) => obj is Case5 c && Equals(c);
            public override int GetHashCode() => EqualityComparer<T5>.Default.GetHashCode(V);
            public override string ToString() => Union.ToString<TType, T5>(V);
        }
    }
}