Recursive discriminated union case types

Question

How can I create OCaml/F# DU type where its cases are subsets of other cases?

For example, I want to make a symbol table which contains different symbol declaration types, such as program types, variables and functions.

At first glance, I can see that a variable contains its type, function also contains a type and many parameter variables. So I'd like to use 1 DU, instead of seperating to many records or aliases:

type Symbol =
    | TypeSymbol of id:string
    | VariableSymbol of id:string * type':TypeSymbol
    | FunctionSymbol of id:string * params':VariableSymbol list * type':TypeSymbol

But this is wrong, because the DU cases cannot be subsets of other cases. How can I reformat types to declare that DU cases are recursive to each other?

Answer 1

For F#, the simplest solution would be to create smaller single-case DUs and reference those:

type T = T of id:string
type V = V of id:string * type':T
type Symbol =
   | TypeSymbol of T
   | VariableSymbol of V
   | FunctionSymbol of id:string * params': V list * type':T

Its usage through decomposition could be something like this.

let rec print x = 
   match x with
   | TypeSymbol (T typeId) -> 
      typeId

   | VariableSymbol (V (varId, T typeId)) -> 
      sprintf "%s : %s" varId typeId

   | FunctionSymbol (funId, params', T typeId) ->         
      let printedParams = 
         params'
         |> List.map (VariableSymbol >> print) 
         |> String.concat ") -> ("
      sprintf "%s = (%s) -> %s" funId printedParams typeId