haskell中的递归数据结构:类似prolog的术语

Question

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

我想用Haskell Prolog之类的术语编码,但我想出的每个解决方案都有不同的缺点,我真的想避免.如果你希望从这个角度来看我的问题,我想找到一种在Haskell类型中编码BNF语法的廉价而优雅的方法.

正如一个提醒,一些序言而言可能是male,sum(2, 3.1, 5.1),btree(btree(0, 1), Variable).

解决方案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}

在这个变体中,我可以清楚地区分谓词和基本术语,但是列表中的Either类型在predArgs后面的代码中管理会非常麻烦(我想......我是Haskell的新手).

解决方案3

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

data Predicate = Predicate String [Term]

使用这个最后的解决方案,我像以前一样将术语分成两种不同的类型,但这次我避免Either Term Predicate添加一个Struct构造函数,Term其语义基本相同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]