How to define discriminated unions using records?

[alrz]

Take a tree structure where a hierarchy of types are needed (i.e. not flat). How would you define such tree using records?

RootNode
   | AbstractNode(int Data)
       | LeafNode(int Left, int Right)
       | ...
   | SealedNode()
   | ...

Using classes, there's much boilerplate code to write. I'm particularly interested to see how records could improve that.

[CyrusNajmabadi]

Can you explain this bit:

 AbstractNode(int Data)
       | LeafNode(int Left, int Right)

so abstract nodes can contain data. But leafnodes (which are, aren't abstractnodes?) can/cannot?

[alrz]

Probably not the best tree representation. Leaf nodes can be either abstract or sealed and both can define fields. Basically a closed hierarchy of types - what I would expect to be able to do with discriminated unions, but I'm guessing records can already help in doing so until we get proper DUs.

[svick]

I'm still confused about the structure you're looking for. Maybe it would help if you showed how it would be defined in a language that already supports DU?

[alrz]

@svick

I'm not aware of any language with non-flat ADT capabilities - not at least in the "concise" form (versus the "expanded" form which would look like scala sum types). The Mode example in this blog post is the closest I could find. Of course each subtype should be able to define its own fields as it is already the case for any language with discriminated union support.

[alrz]

Turns out, simply using record will do the job. If you don't want to deal with base constructor call, you can define fields rather than arguments in primary ctor and value equality still works.

abstract record RootNode {
  public object Data;
  sealed record LeafNode1 : RootNode {
    public int Left, Right;
  }
  sealed record LeafNode2 : RootNode { }
}

To make sure every field gets initialized we probably need dotnet/csharplang#3630

Now the only downside to this is that every field is taken into account for value equality and there is no easy workaround to exclude some except for redefining Equals and GetHashCode completely.

Also it would be nice if empty records gets compiled to singletons out-of-the-box (LeafNode2 example above).