haskell - haskell中的递归数据结构: prolog-like terms

Question

我对 Haskell(我目前正在尝试学习的语言)中的递归数据结构有疑问。

我想用类似 Haskell Prolog 的术语进行编码，但我想出的每个解决方案都有不同的缺点，我真的想避免这些缺点。如果您希望从这个角度看待我的问题，我希望找到一种廉价且优雅的方式在 Haskell 类型中编码 BNF 语法。

提醒一下，一些序言术语可能是 male、sum(2, 3.1, 5.1)、btree(btree(0, 1),变量)。

解决方案1

data Term = SConst String
          | IConst Integer
          | FConst Double
          | Var    String
          | Predicate   {predName :: String, predArgs :: [Term]}

使用此解决方案，我可以使用嵌套谓词(因为 predArgs 是 Term)，但我无法将谓词与类型签名中的其他术语区分开来。

解决方案2

data Term = SConst String
          | IConst Integer
          | FConst Double
          | Var    String

data Predicate = Predicate {predName :: String, predArgs ::[Either Term Predicate}

在这个变体中，我可以清楚地区分谓词和基本术语，但是 predArgs 列表中的 Either 类型对于稍后在代码中的管理来说可能相当麻烦(我认为...我是 Haskell 的新手)。

解决方案3

data Term = SConst String
          | IConst Integer
          | FConst Double
          | Var    String
          | Struct String [Term]

data Predicate = Predicate String [Term]

通过最后一个解决方案，我像以前一样将术语拆分为两种不同类型，但这次我避免使用 Either Term Predicate 在 Term< 中添加 Struct 构造函数 与 Predicate 具有基本相同的语义。

这就像解决方案 1 一样，有两个术语谓词构造函数。一种是支持递归的，Struct，另一种是Predicate，能够区分谓词和正则项。

此尝试的问题是 Struct 和 Predicate 在结构上是等效的并且具有几乎相同的含义，但我将无法编写有效的函数 -示例 - 均在 (Predicate "p"[]) 和 (Struct "p"[]) 上。

所以我的问题是:请问有没有更好的方法来编码我的谓词和术语，以便:

1. 我能够区分类型签名中的谓词和术语；
2. 支持诸如 p(q(1), r(q(3), q(4))) 之类的嵌套谓词；
3. 我可以编写在谓词上统一工作的函数，而不需要任何与解决方案 #3 中的区别类似吗？

如果您需要任何进一步的说明，请随时向我询问。

非常感谢。

Answer 1

您可以添加术语构造函数来包装谓词。在这里，我还将所有文字分解为它们自己的数据类型:

data Term = TLit    Literal
          | TVar    String
          | TPred   Predicate

data Literal = LitS String
             | LitI Int
             | LitF Double

data Predicate = Predicate String [Term]