递归区分的联合案例类型

Question

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

例如，我想制作一个符号table，其中包含不同的符号声明类型，例如程序类型、变量和函数。

乍一看，我可以看出一个变量包含它的类型，函数也包含一个类型和许多参数变量。所以我想使用 1 个 DU，而不是分隔成许多记录或别名：

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

但这是错误的，因为 DU 案例不能是其他案例的子集。我如何重新格式化类型以声明 DU 案例相互递归？

Answer 1

我从未使用过它们，但我认为您想使用 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

如您所见，如果我尝试使用 TypeSymbol 以外的其他东西构建它，OCaml 将不允许我使用构造函数 VariableSymbol 创建符号。

请参阅 here 手册，祝您使用顺利。

Answer 2

对于 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

递归区分的联合案例类型

Recursive discriminated union case types

f#

ocaml

record

abstract-syntax-tree

discriminated-union