Recursive discriminatory types of association cases

Question

How can I create an OCaml / F # DU type, where its cases are a subset of other cases?

For example, I want to create a character table that contains various types of character declarations, such as program types, variables, and functions.

At first glance, I see that the variable contains its type, the function also contains the type and many parameter variables. Therefore, I would like to use 1 DU instead of splitting into 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 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 one-dimensional DUs and reference them:

 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 use through decomposition may 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 

Answer 2

I never used them, but I think you want to work with GADT (this answer is for OCaml):

 type ts type vs type 'a symbol = | TypeSymbol : {id : string} -> ts symbol | VariableSymbol : {id : string; ty : ts symbol} -> vs symbol | FunctionSymbol : {id : string; params : vs symbol; ty : ts symbol} -> 'a symbol;; (*don't use "type" as a field name since it a keyword of OCaml*) 

As you can see, this allows me to specify exactly with which constructors I build my constructors.

Now that I want to use them:

 # let t = TypeSymbol {id = "a"};; val t : ts symbol = TypeSymbol {id = "a"} # let v = VariableSymbol {id = "b"; ty = t};; val v : vs symbol = VariableSymbol {id = "b"; ty = TypeSymbol {id = "a"}} # let ve = VariableSymbol {id = "c"; ty = v};; Characters 41-42: let ve = VariableSymbol {id = "c"; ty = v};; ^ Error: This expression has type vs symbol but an expression was expected of type ts symbol Type vs is not compatible with type ts 

As you can see, OCaml will not allow me to create a character with the VariableSymbol constructor if I try to build it with something other than TypeSymbol .

See here for guidance and good luck with their use.