Discussion: Unions/closed hierarchies/ADTs, which one does C# 7.1+ need & what would the spec look like?

[DavidArno]

[Please note, I'd like to use this thread to build a proper proposal for union types in C#, so this will be edited over time to take into account feedback to build it into a proposal]

A group of related features requested many times in the Roslyn repo is for something similar to F#'s discriminated unions. The proposals use various names for these type collections: unions, ADTs (arithmetic data types), closed hierarchies, hierarchy data types etc.

In addition, numerous different syntaxes have been proposed, re-using enum. abstract and sealed to denote it's a union as well as varying greatly in the syntax within the type.

Lastly, just to add to the confusion, separate proposals for enum types similar to that supported by Java have also come and gone. These threads then often morph into discussions around unions too.

Rather than list all the existing proposals, the following two seem a useful starting point as they then link to many of the other proposals:
[C# Feature Request] Hierarchy Data Type
Proposal: Add Discriminated Unions using a new Type

Please note, this proposal doesn't cover closed sets of values, as discussed in Proposal: Record Enum Types as they potentially infringe on a Java "patent" (see that thread for details). It is only concerned with closed sets of types.

Declaring a union

An example of a union from F# for fun and profit is:

type Person = {first:string; last:string}  // define a record type 
type IntOrBool = I of int | B of bool

type MixedType = 
  | Tup of int * int  // a tuple
  | P of Person       // use the record type defined above
  | L of int list     // a list of ints
  | U of IntOrBool    // use the union type defined above

Using C# records, this could potentially be expressed in C#, using a form of union definition syntax, as:

class Person(string first, string last); // define a record type
enum class IntOrBool { int I; bool B; }

enum class MixedType
{
    (int, int) T;
    Person P;
    IList<int> L;
    IntOrBool U;
}

Constructing a union instance

As the underlying type of the above union is MixedType, it might be necessary to use the following syntax to construct them:

var tuple = new MixedType.T(1, 1);
MixedType list = new MixedType.L(new List<int> { 1, 2 });

It would be desirable to be able to express it as following though, but this could lead to name resolution issues(?):

var tuple = new T(1, 1);
MixedType list = new L(new List<int> { 1, 2 });

i,e, the MixedType part has been dropped and the "subtype" names are used directly.

Pattern matching

Using the "subtype" names directly and the upcoming match expression, a pattern match of a union might look like:

var x = tuple match (
    case T (x, y) : x + y,
    case U intOrBool when intOrBool is int i : i,
    case * : 0
);

Generics

The exemplar union type of Option<T. (chosen over Maybe<T> as the former is used by F#) could be declared as:

struct None { ... }

enum struct Option<T>
{
    None None;
    Some Some<T>(T value);
}

Obvious questions

• What do we call them? Discriminated unions seems the obvious choice to me, as that's what F# uses. What merit would other terms bring us?
• Is the syntax used above a good choice, or could it be expressed in a better form?
• Can this all be achieved without CLR changes? (I'm assuming yes, as F# does it)
• What does the union declaration get converting into? (much like records, the above syntax is effectively hiding lots of boilerplate code. What is that code)?
• Can structs be used for unions? How would a var x = default(MixedType) handled, to ensure it results in a meaningful value?
• What other questions need asking and answering?

[orthoxerox]

Does your approach allow nested records? Let's say I want to express something like this in C#:

type Expr =
  | Const of int
  | Bin of Op * Expr * Expr

except Const and Bin are proper subtypes of Expr, not tags on tuples.

[gulshan]

• I think it's better to separate the normal/current enum- closed set of named values sharing same type and DU/ADTs- closed set of types sharing same base type.

• Value enums can be extended to inherit any other types- numeric types, structs, unnamed tuples and classes. Currently it is limited to variants of integer type. This inheritance can just use current syntax for inheriting integers. This might look like-

public struct Color(int R, int G, int B);
public enum CommonColors : Color
{
    Blue  = new Color(0, 0, 255),
    Green = new Color(0, 255, 0),
    Red   = new Color(255, 0, 0)
}

Or using tuples-

public enum CommonColors : (int Red, int Green, int Blue)
{
    Blue  = (0, 0, 255),
    Green = (0, 255, 0),
    Red   = (255, 0, 0)
}

• If a subtype of a DU directly wants to inherit another type instead of defining new type, there would be a problem of supporting multiple inheritance I guess. In that case, the DU type can be an interface instead of a class or struct. This interface can internally implement tags etc. The subtypes should also be able to inherit numeric types like int, literal constants like true, 0 or "C#" or a subtype can be a name-only type without any definition like Nil. The name-only subtype has a single value- denoted by the type name. In that case, the MixedType will look like-

class Person(string first, string last); // a record type
enum interface IntOrBool
{
    class I: int;
    class B: bool;
}

enum interface MixedType
{
    class T: (int, int);
    class P: Person;
    class L: IList<int>;
    class U: IntOrBool;
}

I would really like to use a new keyword type instead of interface here. Along with this assumed keyword, we can go for a hierarchical DU-

enum type MixedType
{
    class T(int first, int second);
    class Person(string first, string last);
    class L: IList<int>;
    class U: enum type IntOrBool
    {
        class I: int;
        class B: bool;
    };
}

The Option type will be-

enum type Option<T>
{
    class None;
    class Some: T;
}

Similarly the Result type will be-

enum type Result<T>
{
    class Success: T;
    class Failure: Exception;
}

[gulshan]

@orthoxerox This F# DU-

type Expr =
  | Const of int
  | Bin of Op * Expr * Expr

will become this in C# according to my proposal-

enum type Expr
{
    class Const: int;
    class Bin: (Op, Expr, Expr);
}

[gafter]

/cc @agocke

[ufcpp]

IMO, anonymous types and named types might have to be compatible, or at least should be consistent.
For instance, in the case of Product Types:

	anonymous	named
C# feature	Tuples	Records
declaration	struct Point(int x, int y); Point p;	(int x, int y) p;
construction	new Point(1, 2)	(1, 2)
deconstruction	p is Point(var x, var y)	p is (var x, var y)
conversion	Point p = (Point)(1, 2);	(int x, int y) t = (int x, int y)new Point(1, 2);

This might apply to Unions too. So isn't it necessary to discuss also about anonymous unions?
TypeScript has anonymous Union Types: https://www.typescriptlang.org/docs/handbook/advanced-types.html

function padLeft(value: string, padding: string | number) {
    // ...
}

I want both named and anonymous Unions in C# and their syntax are consistent. e.g.

	anonymous	named
declaration	`enum type X : int	string; X p;`

[DavidArno]

@gulshan,

I don't believe that DU's should be limited to a set of types with a common base type. It probably makes sense to maintain as much compatibility with F# DU's as feasible, as that could even then allow them to be used interchangeably.

However, looking at your examples, I may simply be misunderstanding what you mean as you then show union types with no common base type.

[DavidArno]

@gafter, as there is now a championed issue (#113) for this proposal, should I close this one?

[gulshan]

In my proposal, I am using a special sealed, internally-auto-implemented kind of interface as a base type, instead of an abstract class. Because class as a base type will require multiple inheritance of some sort. So, in this example (using interface for clarity)-

enum interface Result<T>
{
    class Success: T {}
    class Failure: Exception {}
}

Result<T> is actually that special sealed(cannot be implemented outside itself) interface, while Success and Failure are two classes implementing interface Result<T>. So, where are the interface methods and their implementations? They are hidden and managed internally. Does this proposal serve the purpose of DUs? Or, a class is required as a common base type? And what should be done to maintain compatibility with F#?

[gafter]

@DavidArno I do not expect to spend much time on DUs until the work on records settles down. I leave it to you to decide where best to continue conversations about approaches to DUs.