递归区分的工会案例类型

Question

如何创建OCaml/F＃DU类型，其案例是其他案例的子集？

例如，我想创建一个包含不同符号声明类型的符号表，例如程序类型，变量和函数。乍一看，我可以看到一个变量包含它的类型，函数也包含一个类型和许多参数变量。所以我想用1 DU，而不是向分隔条件多条记录或别名：

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

但这是错误的，因为杜情况下不能是其他情况的子集。我如何重新格式化类型来声明DU个案是递归的？

Answer 1

F＃的，最简单的解决办法是建立较小的单例的DU和引用这些：

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 

它通过分解用法可能是这样的。

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

我从来没有使用过，但我想你想与GADT工作（这个答案是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's a keyword of OCaml*) 

正如你所看到的，这让我有什么构造确切指定我建立我的构造函数。

现在，当我想使用它们：

# 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 

正如你所看到的，OCaml中不会让我创造一个符号与构造VariableSymbol如果我尝试以比TypeSymbol别的东西来构建它。

请参阅here手册，祝您好运。