是否有带有显式子类型的 ADT 名称？

Question

我正在寻找将 ADT 与显式子类型相结合的数据类型的正确名称。

在我的一个应用程序中，我使用类似于 ADT 的结构来表示解析树，并在其上执行递归模式匹配。我发现如果我可以将 ADT 与子类型结合起来会很方便，如下例所示：

注意：示例是用 Haskell 的语法编写的，但这不是 Haskell 代码。

data Empty = Empty
data Expr = Int Int | Add Expr AddOp Expr
data OptionalExpr =
| Empty  // I want to make Empty a subtype of OptionalExpr
| Expr   // I want to make Expr  a subtype of OptionalExpr

在上面的例子中，我首先定义了两种类型：Empty 和 Expr。然后我将这两种类型作为 OptionalExpr 的子类型。我意识到这种数据类型并不常见。显然 Haskell 和 OCaml 都不支持它。但我不知道其他函数式语言。

我正在寻找将 ADT 与显式子类型相结合的东西，而不是像多态变体那样结构隐含的子类型。这个要求有几个理由：

• 首先，我们想要全有或全无的子类型。假设我们希望 A 是 B 的子类型，那么我们将永远不想只在 B 下包含 A 的一些变体。要么 A 是 B 的子类型，在这种情况下 B 包括 A 的所有变体，或者 A 是不是 B 的子类型，在这种情况下，B 不包括 A 的任何变体。我们不允许中间有灰色区域。
• 其次，我们不希望 B 在任何意义上都是开放的。我们想到了 B 的一组非常具体的子类型。我们不希望某些东西仅仅通过实现一个类型类或类似的东西就成为 B 的一个实例。
• 第三，假设 A 型有大量变体。我们想让类型 B 成为 A 的超类型。将所有变体复制到 B 中，正如多态变体所要求的那样，太麻烦且容易出错。
• 第四，当我们只想表达一个子类型时，我们不想引入新的值构造函数。在上面的例子中，我们可以这样写OptionalExpr作为ADT与2值构造，像这样：data OptionalExpr = EmptyExpr | NonEmptyExpr Expr或者我们也可以使用Maybe，但在我的应用程序，这是不能接受的，因为嵌入的水平可以说是相当深刻的，它会解构像(L1 (L2 (L3 (L4 (L5 value_wanted))))).

为了让您了解为什么存在此类要求，我在下面展示了一个更具体的示例：

PrimaryExpr = ID | LeftParen Expr RightParen
UnaryExpr = PrimaryExpr | NegateOp PrimaryExpr    // -
MultExpr  = UnaryExpr | MultExpr MultOp UnaryExpr // *
AddExpr   = MultExpr  | AddExpr  AddOp MultExpr   // +
CompExpr  = AddExpr | AddExpr CompOp AddExpr
Expr = CompExpr

上面的例子表达了一个子类型层次结构，表达了诸如AddExpr是一个CompExpr，但是一个CompExpr不是一个AddExpr这样的想法。对于这个特定的例子，有些人向我建议我可以用 Expr 替换 UnaryExpr、MultExpr、AddExpr 等。也就是说，我可以将所有类型定义为单一类型。这会丢失类型约束，例如 CompExpr 不是 AddExpr，并且因为我正在对这些类型进行递归模式匹配，所以我需要静态强制执行此层次结构的约束。

我在文献中寻找的这种数据类型有名称吗？还是我在寻找甚至没有意义的东西？如果你认为是这种情况，我为什么要寻找一些荒谬的东西？感谢您的指点。

编辑：尽管我已经用 Haskell 的语法编写了上面的代码片段，但我不是在 Haskell 中编写我的应用程序。我使用我自己的语言和我自己的数据类型，所以我不受 Haskell 语义的限制。我正在寻找指向文学中类似概念的指针，这样当我为我的项目编写报告时，我似乎不会重新发明新的东西。我尝试了所有我能想到的谷歌关键字，但没有任何正确的返回，所以我在这里问。

Answer 1

除非我误解了，多态变体几乎可以做到这一点。然而，“未标记的联合”并不是一个很好用的术语（我想大多数人会认为您正在要求 C 风格的联合）。

该示例如下所示：

type empty = [`Empty]

type bin_op = Add | Sub

type expr = [`Int of int | `Add of expr * bin_op * expr]

type optional_expr = [empty | expr]

type weird_expr = [expr | `Wierd of expr | `Zonk of string]

请注意，对于 OCaml 的多态变体，子类型关系是在结构上定义的，而不是在命名类型之间定义的。