如何在Haskell中建模层次数据类型？

Question

我有一堆类型，它们的层次结构存储了一些有用的信息。我试图避免在操作它们的函数中嵌入类型层次结构的知识。

以下是斯坦福自然语言处理中的Typed Dependencies的摘录：

root - root
dep - dependent
  aux - auxiliary
    auxpass - passive auxiliary 
    cop - copula
  arg - argument 
    agent - agent

我希望创建一些数据类型，以反映此结构，以便我可以定义一些仅能在特定类型上操作的函数。当我有一个操作arg的函数时，用于表示arg的类型还应包含agent，但表示agent的类型不应包含arg。表示dep的类型应包括其下面的所有内容。

在Haskell中是否可能实现这一点？我一直在尝试声明不同的data类型来模拟它，但由于一个数据类型不能使用另一个数据类型的构造函数，因此我无法让它起作用。

我怀疑这种方法在Haskell中可能不太可行，如果是这种情况，那么通常如何处理这些情况，其中压平层次结构绝对不可取？

- Isaac

---

最简单的方法是拥有一个具有Agent字段的Arg数据类型。那样是否足够？ - danidiaz

@danidiaz 这将违反这个要求：“当我有一个操作参数的函数时，用于表示参数的类型也应包括代理”。 - Julia Path

这可能是一个有趣的相关阅读：https://wiki.haskell.org/OOP_vs_type_classes - E4z9

https://hackage.haskell.org/package/subhask-0.1.1.0/docs/SubHask-SubType.html - Alec

@Alec 所有类型都将具有文本字段，dep 的成员还具有额外的关系字段。重要的是，类型本身传达了有关关系上下文的一些有用信息。随着您向下遍历层次结构，上下文变得更加具体。 - Isaac

Answer 1

总的来说，子类型在Haskell中并不太好处理。但是，如果你只是试图建模（非多重）继承（因此你有一个子类型树而不是格），你实际上可以使用类型类构建子类型。这里有一个简短的gist，正好做到了这一点。从那里开始工作，你定义你的数据类型。

data Root = Root ...
data Dep = Dependent ...
data Aux = Auxiliary ...
data AuxPass = PassiveAuxiliary ... 
data Cop = Copula ...
data Arg = Argument ...
data Agent = Agent ...

和相应的实例

instance Subtype Aux where
  type SuperType Aux = Dep
  embedImmediate = ...

instance Subtype AuxPass where
  type SuperType AuxPass = Aux
  embedImmediate = ...

instance Subtype Cop where
  type SuperType Cop = Aux
  embedImmediate = ...

instance Subtype Arg where
  type SuperType Arg = Dep
  embedImmediate = ...

instance Subtype Agent where
  type SuperType Agent = Arg
  embedImmediate = ...

你如何填写...取决于你自己。以下是一些建议：

• 如果你的子类型在超类型上添加了许多字段，请始终添加一个具有超类型的字段，并使embedImmediate返回该字段。
• 如果你的子类型仅添加了几个字段，则可能需要手动拆包。你的data定义会更整洁，但embedImmediate定义会稍微长一些。
• 如果你的子类型没有向超类型添加任何字段，则可以在超类型周围创建一个newtype，并使用Data.Coerce中的coerce函数进行embedImmediate赋值。

然后，你不能在期望超类型的函数中完全使用子类型，但几乎可以：你只需要添加一个调用embed（与embedImmediate不同！）以从子类型转换为所需的任何超类型（基于类型推断）。您可能想查看some example uses。

请注意，现在您可以将<:用作约束条件：例如，是Aux的子类型的某些东西的类型为(a <: Aux) => a。每当您希望此内容被视为Aux（或Aux的超类型）时，请对其调用embed。

这种方法的一个明显缺点是必须注明输入和输出类型（否则不清楚你想要将哪个超类型嵌入，会出现“模糊类型”错误）。如果您已经写了很多签名，那么应该没问题。

- Alec

Answer 2

使用类型类。

首先，将每个具体类型定义为单独的数据声明。

然后，对于每个具有子类型的类型，声明一个类型类，并在其父类上添加约束。这种关系的示例是预设中的 Functor => Applicative => Monad 结构。

因此，要定义示例结构：

class Root where
    ...

class Root => Dep where
    ...

class Dep => Aux where
    ...

class Aux => Auxpass where
    ...

class Aux => Cop where
    ...

class Dep => Arg where
    ...

class Arg => Agent where
    ...

- user1937198

---

为什么这个被踩了？我知道这不是类型类的理想用法，但有没有其他选择？这个加上 GADT 行不行？ - Isaac

不是恶意评分，但可能是因为你仅仅将类型类作为重载的手段而非抽象化的手段。我不建议这种方法，但指出这一点并不是一个坏主意。 - Alec