Mutually referring cases in Discriminated Unions allowed in F#?

Question

The following discriminated union fails to compile:

type Expression =
  | Identifier of string
  | Integer of int
  | Assignment of Identifier * Expression

with the shown error being

The type "Identifier" is not defined.

on the last union case.

I've tried tagging Expression with the rec attribute but that seems of no avail.

Is there a work-around for this? Better yet, is the referred reason the cause of my trouble?

Answer 1

You cannot do that. Inside the Union you cannot refer to another Union element.

So it should be:

type Expression =
  | Identifier of string
  | Integer of int
  | Assignment of Expression * Expression

So that when you parse the assignment union you can put a validation there that the first Expression in the tuple should be Identifier.

Answer 2

It sounds like you actually want

| Assignment of string * Expression

or alternatively

type Id = Id of string
type Expression =
    | Identifier of Id
    | Integer of int
    | Assignment of Id * Expression

if you want an extra nominal type for all identifiers.

It is best to exclude meaningless values in the type system when possible (meaningless states should not be representable), which is why I'd avoid Expression on the left hand side of an assignment if your language doesn't need that.

In any case, the reason it's not allowed is because Identifier is not a type (Expression is).