Champion "Discriminated Unions"

[gafter]

• Proposal added
• Discussed in LDM
• Decision in LDM
• Finalized (done, rejected, inactive)
• Spec'ed

See

• Proposal: Add completeness checking to pattern matching draft specification roslyn#188
• Discussion: Unions/closed hierarchies/ADTs, which one does C# 7.1+ need & what would the spec look like? #75
• https://github.com/dotnet/csharplang/blob/master/meetings/2017/LDM-2017-01-10.md
• Proposal: "Closed" type hierarchies #485

Design meetings

https://github.com/dotnet/csharplang/blob/main/meetings/2022/LDM-2022-08-31.md#discriminated-unions
https://github.com/dotnet/csharplang/blob/main/meetings/2022/LDM-2022-09-26.md#discriminated-unions
https://github.com/dotnet/csharplang/blob/main/meetings/2024/LDM-2024-07-24.md#discriminated-unions

[gafter]

I wouldn't expect progress on this feature to precede records.

[DavidArno]

@gafter,

I've started writing a draft proposal around #75. Would you like me to continue with this, or did you have a proposal planned yourself?

[gafter]

@DavidArno I do not expect to invest any significant effort on this until we make progress on records.

[DavidArno]

@gafter,

OK, that's good to know. I'll carry on with my proposal then, but will take time over it as there's no rush.

[gafter]

/cc @agocke

[agocke]

I will be moving my proposal of "closed" type hierarchies from Roslyn to this repo shortly. I also think we should explore "real" discriminated unions and have some thoughts on that, but it's still much more of an exploratory phase for me.

However, I think I'm close to a reasonably complete proposal for closed and an analyzer-based prototype. I'll happily champion this feature, as well.

[Richiban]

One question that I think we need to ask (and I haven't seen anyone ask elsewhere) is whether the case classes can be used as types.

Allow me to illustrate with the example of the Option type:

public enum class Option<T>
{
	None,
	Some(T Value)
}

Obviously Option<T> is a type (an abstract base class), but are None and Some types? Since, in an OO language like C#, ADTs are probably actually implemented as type hierarchies one might be tempted to answer "yes", but I'm not sure it makes much sense.

public void MyMethod(Some<string> someString) // Is this allowed? It doesn't make much sense
{
	// ...
}

I think of ADTs as functioning more like enums, however they're actually implemented. So using each case as a type doesn't make sense, any more than this makes sense:

public enum Colours
{
	Red, Green, Blue
}

public void MyMethod(Blue colour)
{
	// ...
}

[alrz]

whether the case classes can be used as types.

I think it shouldn't be the case with enum class but with another "expanded" syntax which could represent more complex type hierarchies like an AST

class SyntaxNode {
  case class Statement { } // implicitly inherit from SyntaxNode, as in, a "case" of the said type
  case class Expression {
     case enum class Literal { Numeric, String }
  }
}

[mcintyre321]

I think that feature can be added fairly simply using a custom type, in the same way Tuple<T0, ..., TN> was added.

I maintain a library, OneOf, which adds a OneOf<T0, ..., TN> type which has .Match<TOut>(Func<T0, ..., TOut>, ..., Func<T0, ..., TOut> methods. By using implicit operators to create the OneOf instances from values, the syntax is very terse and comprehensible. Also, the allocations are low because it's a struct and doesn't create intermediate 'builder' objects, unlike some other solutions.

The OneOf<T0, .., TN> type also provides .Switch and .TryGetTX(out TX value, out TRemainder remainer) methods.

Example of using a OneOf as a return value:

public OneOf<User, InvalidName, NameTaken> CreateUser(string username)
{
    if (!IsValid(username)) return new InvalidName();
    var user = _repo.FindByUsername(username);
    if(user != null) return new NameTaken();
    var user = new User(username);
    _repo.Save(user);
    return user;
}

example of Matching

    OneOf<string, ColorName, Color> backgroundColor = "Red"; //uses implicit casts to reduce overhead
    Color c = backgroundColor.Match(
        str => CssHelper.GetColorFromString(str),
        name => new Color(name),
        col => col
   );
    

As new types are added to the OneOf definition, compiler errors are generated wherever the union is Matched or Switched, as the methods are required to have the correct number of lambda parameters.

This can be included in the BCL without language changes, although I'm sure some syntactical sugar could be sprinkled.

---

this proposal was originally made at dotnet/roslyn#14208 and at #1524 . Sorry!

[Richiban]

@mcintyre321 Your OneOf type can be described as equivalent to the Either type or Choice type such as that found in F#. However, the Either type is not an alternative to discriminated unions, in fact it is built on top of discriminated unions:

type Choice<'a, 'b> = Choice1Of2 of 'a | Choice2Of2 of 'b

[HaloFour]

@mcintyre321

While your library does accomplish providing a single discriminated union it also demonstrates the degree of boilerplate required to do so which is what this proposal seeks to reduce. Your types also don't work with C#'s recursive pattern matching which will make it much more efficient and much more capable to match over such a type:

var backgroundColor = ...;

// no delegate invocation required
Color c = backgroundColor switch {
    string str => CssHelper.GetColorFromString(str),
    ColorName name => new Color(name),
    Color col => col
};

[mcintyre321]

@Richiban OneOf<T0, ..., TN> has up up to 33 parameters, so is more useful as a general return object than Either or Choice.

@HaloFour I agree it would be good to have switch and match support built in to the language,. butI would have thought that the delegate calls will be JITted. I'm not sure what the boilerplate you refer to is.

[HaloFour]

@mcintyre321

I'm not sure what the boilerplate you refer to is.

public enum class OneOf<T1, T2>
{
	First(T1 value),
	Second(T2 value)
}

vs. this*

* Yes, I know that you have all of the arities crammed into one, but the file is too large to link to a specific line.

[Richiban]

@mcintyre321 I don't doubt it's usefulness (or the fact that it's better than Either at those situations).

My point was that discriminated unions are a much more general tool that can also solve the problem that Either solves.

I'm not sure how you would propose to implement the equivalent of this using an Either type?

type FavouriteColour =
    | Red
    | Green
    | Blue
    | Other of string

[mcintyre321]

@Richiban The abilities to naming a DU is useful, but you still get a lot of value with anonymous DUs. Is it a show-stopper to not have named unions (initially at least)?

That said, there are some things that can be done.

A OneOf, as implemented, is a struct, but I think that in F# (by default) they are classes. So you could make OneOf a class too*, and have class FavouriteColour : OneOf<Red, Green, Blue, string> { }. One problem with this is that implicit operators aren't inherited, although I think maybe I saw a proposal suggesting that was coming.

Another alternative for naming is to use a Record type e.g. class FavouriteColour(OneOf<Red, Green, Blue, string> Value).

And you can always use an alias: using FavouriteColour = OneOf<Red, Green, Blue, string>; if it's just the code bloat that's a problem (rather than the lack of a named Type ).

I appreciate none of this is quite as nice as the F# approach, but perhaps the language could be extended to fix some of this. E.g. defining a union class FavouriteColour : OneOf<Red | Green | Blue | string> { } could cause the compiler to output the required implicit operators.

TBH I'm happy with any solution where

• you can do ad-hoc definition of DUs in method signatures and member declarations
• concrete types from any library can be used
• exhaustive matching with compile errors after a change in parameters (obv!)

@HaloFour cramming it into one file is along the lines of https://referencesource.microsoft.com/#mscorlib/system/tuple.cs , although I admit OneOf.cs has become somewhat larger!

*There's a class-based OneOfBase in the library, but the name isn't great IMO.

[roboz0r]

I made a proposal in the F# GitHub about a possible way to implement overlapped struct unions given the current runtime limitations fsharp/fslang-suggestions#1333

[agocke]

FWIW any overlapping is probably trading size for throughput. Having a fixed-address offset, as opposed to a dynamic dispatch, will likely speed up the instruction pipeline.

[agocke]

I'll also say that I don't think Option<T> is a good candidate for "basic" discriminated unions because it has a very specific optimization (use a null pointer for None) that will not be available to any other type or runtime structure.

I think Option is a good candidate for dedicated behavior, both because of it's particular characteristics and the prominence of the use case.

Once we think about special-casing Option, the rest of the overlap use cases seem much less important to me.

[HaloFour]

@agocke

I'll also say that I don't think Option<T> is a good candidate for "basic" discriminated unions because it has a very specific optimization (use a null pointer for None) that will not be available to any other type or runtime structure.

How would that work if T is a value type, and you don't want to box?

[snarbies]

I'm sure this has come up before, but sometimes null is among your inhabited values.

[TehPers]

The niche optimization that Rust performs on its enums is what lets it treat an Option<NonNullPtr> (where NonNullPtr is one of the many non-null pointer types in Rust) as the same size as a NonNullPtr (since NonNullPtr has null as a niche value), but I'm not sure how common that usage would be in C# for an Option<T> value type, and I'm also curious if there's a demand for that kind of optimization in C# anyway. Not that optimizing it if possible isn't a good thing, I just don't know how common it would be, especially since reference types in C# are all nullable anyway. As for enums, unlike Rust, C#'s enums can hold any value that their backing type can hold (so they function essentially as integers), so enums don't really have niche values either. One example of where it might come up that comes to mind is if you nest another value type that can use some padding bytes to store the variant, but I have no clue how possible that is with the current runtime.

[CyrusNajmabadi]

As a point of clarification @TehPers, what you are calling "that kind of optimization in c#" would likely be better described as "that kind of optimization in .net". Layouts of objects, and special things around null-handling, are def in in the purview of the runtime vs the language. :)

[roboz0r]

FWIW any overlapping is probably trading size for throughput. Having a fixed-address offset, as opposed to a dynamic dispatch, will likely speed up the instruction pipeline.

In my proposal the address offsets are fixed at compile time and there's no dynamic dispatch. The tradeoffs are to work around the runtime limitations:

• Generics are not permitted
• Containing a reference type is not permitted

[orthoxerox]

I'm sure this has come up before, but sometimes null is among your inhabited values.

This means that the type should have two representations: one for value types and nullable reference types, the other for non-nullable reference types. If only C# had definitely non-nullable types...

[agocke]

@agocke

I'll also say that I don't think Option<T> is a good candidate for "basic" discriminated unions because it has a very specific optimization (use a null pointer for None) that will not be available to any other type or runtime structure.

How would that work if T is a value type, and you don't want to box?

By special-casing, I mean special-casing in the runtime, similar to Nullable<T>. The runtime can know whether an instantiation is a reference type or value type. In the case of a value type it would store an extra field for None. In the case of a non-null reference type, it would be lowered to null. This would involve also teaching the runtime about reference nullability and enforcing it in at least this case.

[jkone27]

would be great if for Option and Result existing FSharp.Core could be used or shared between roslyn and C#? to mantain some level of compatibility and also many parts of these are just already in place in F#?

*FSharp.Core: Result
*FSharp.Core: Option

why can't C#/Roslyn use FSharp.Core for this feature to some extent? this would allow all existing F# Result and Option types from libraries to be consumable from C# as well, plus, would make future C# result/options consumable from F#

i am sure most likely there is reasons, but just double checking/curious

[HaloFour]

why can't C#/Roslyn use FSharp.Core for this feature to some extent?

F# employs a lot of custom metadata from F# specific assemblies, plus a binary resource blob of additional metadata. I would expect that as a part of this proposal that the C# team will come up with language-agnostic metadata (e.g. attributes defined in BCL assemblies) and convention, and that the F# team could then hopefully adopt that metadata to enable those types to interoperate.

[MgSam]

The latest proposal for this dropped a few days ago: https://github.com/dotnet/csharplang/blob/main/proposals/nominal-type-unions.md

Some initial thoughts:

• I don't see why reference types should be disallowed as part of a type union. This would significantly limit the utility of the feature. The overwhelming majority of existing types out there are reference types. In fact, the examples already break this rule by showing type unions which include string.
• A little confused about why it would be useful for the union itself to implement an interface. A more fleshed out example would be useful.
• Unknown Unions- "Note: It is possible that a future version of the runtime may become type union aware and allow type tests in generic-only contexts to succeed." - having OfType() fail in one version and succeed in the next would be a huge breaking change for the runtime to make. It seems to me this either needs to work in v1 or never.

[mattwar]

@MgSam, reference types are not disallowed, ref types are disallowed. Like 'ref int', or Span. At least for this proposal currently.

[jaredpar]

A little confused about why it would be useful for the union itself to implement an interface.

Why would we want to limit unions from implementing interfaces? They're just another kind of type and it's reasonable for them to implement interfaces like any other type. Consider IEquatable<T> as an example.

[AartBluestoke]

" a huge breaking change for the runtime to make. It seems to me this either needs to work in v1 or never."

• not a breaking change if it is documented as current "known behavior", it is a v1 implementation detail that people need to be aware of when using unions.
• something that could be headed off with a compiler warning for using x<Union>.ofType(...) to let people know when the compiler can tell it is an always false match (as per the example )
  List<Pet> pets = [new Dog(...), new Cat(...)]; pets.OfType<Dog>() // will never match

[MgSam]

@MgSam, reference types are not disallowed, ref types are disallowed. Like 'ref int', or Span. At least for this proposal currently.

Whoops! Thanks for the clarification. 🙂 Too many overloaded words 😅

[MgSam]

Are there any thoughts on a possible anonymous form of unions? In TS, it's extremely common to use union types inline in method signatures rather than declaring them separately.

[Richiban]

The doc has this example:

    public union Option<TValue>(Some<TValue>, None)
    {
        public record struct Some<TValue>(TValue Value);
        public record struct None();
    }

I could be wrong, but if the Some case is nested then it doesn't need to be generic itself, does it? This would effectively be the same:

    public union Option<TValue>(Some<TValue>, None)
    {
        public record struct Some(TValue Value);
        public record struct None();
    }

[mattwar]

The Option type is not in this proposal. It will be in a separate proposal.

[Richiban]

The nesting of case types inside the type union declaration is not a requirement.

Sorry, it may just be your wording and the comment you were replying to, @mattwar , but can you explain? OptionT is fundamentally different from common union types like EitherT in that you can build a tower. e.g. Option of-an Option`T. The ability for the compiler to efficiently handle this does seem like a good requirement.

@jzabroski I'm pretty sure mattwar is referring to the definition of a union, and saying that the union is flexible as to whether its cases are defined inside or outside:

    public record struct A(TValue Value);
    public record struct B();
    public union C<TValue>(A<TValue>, B);

// or

    public union C<TValue>(A<TValue>, B)
    {
        public record struct A(TValue Value);
        public record struct B();
    }

[jcdickinson]

I don't believe Option would be sound with this type of union. While the compiler will warn (should be an error) about this: Option<Foo> = default, it won't warn here: new Option<Foo>[5]. This means that Option would be unavoidably 3-state: Some, None, and default (inner null) - making it strictly worse than null (especially for exhaustiveness checking).

[FaustVX]

In the proposal, they talk about defaultable union (https://github.com/dotnet/csharplang/blob/main/proposals/nominal-type-unions.md#default-unions)
So the Option<T> could be :

readonly struct None();
union Option<T>(Some<T>, None = default)
{
  public record readonly struct Some(T Value);
}

This way, array of Option<T> contain only None values.

[mattwar]

It is true, a type union based on a struct wrapper always has a default value. Just like a type union base on a reference type can also be null. It is the same problem as non-nullable reference types. The best we can do is add warnings when the compiler can determine you are creating this default state.

[mattwar]

There is a discussion started for this new proposal here:
#9410