Skip to content

Instantly share code, notes, and snippets.

@dadhi
Last active March 11, 2019 11:03
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save dadhi/7bd19c6c2de767dd1bc77baf8f7670aa to your computer and use it in GitHub Desktop.
Discriminated Union or ADT Sum-type in C#
// main.cs
// Created by dadhi on 2018/09/12
// MIT licensed to Maksim Volkau 2018-2019
using System;
using System.Collections.Generic;
using static System.Console;
// 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 DU sub-typing
public sealed class FlagOrName : Union<FlagOrName, bool, string> { }
// A different type from FlagOrName
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);
}
// 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 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; }
}
/// 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;
public static class Union
{
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 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 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 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 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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment