4

我对 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]}

使用此解决方案，我可以嵌套谓词（因为predArgsare 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与.TermPredicate

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

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

所以我的问题是：拜托，有没有更好的方法来编码我的谓词和术语，例如：

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

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

非常感谢。

4

2 回答 2

7

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

data Term = TLit    Literal
          | TVar    String
          | TPred   Predicate

data Literal = LitS String
             | LitI Int
             | LitF Double

data Predicate = Predicate String [Term]
于 2011-09-27T19:41:45.730 回答
2

这是一种方法（这可能不值得麻烦）：

{-# LANGUAGE EmptyDataDecls #-}

-- 'T' and 'F' are short for 'True' and 'False'
data T = T
data F

-- 'p' is short for 'mayNotBeAPredicate'
data Term p
    = SConst !p String
    | IConst !p Integer
    | FConst !p Double
    | Var    !p String
    | Predicate {predName :: String, predArgs :: [Term T]}

sconst :: String -> Term T
iconst :: Integer -> Term T
fconst :: Double -> Term T
var :: String -> Term T
predicate :: String -> [Term T] -> Term p
sconst = SConst T
iconst = IConst T
fconst = FConst T
var = Var T
predicate = Predicate

checkPredicate :: Term p -> Maybe (Term F)
checkPredicate (Predicate name args) = Just (Predicate name args)
checkPredicate _ = Nothing

forgetPredicate :: Term p -> Term T
forgetPredicate (SConst _ s) = sconst s
forgetPredicate (IConst _ i) = iconst i
forgetPredicate (FConst _ f) = fconst f
forgetPredicate (Var    _ s) = var s
forgetPredicate (Predicate name args) = predicate name args

您现在可以编写只接受谓词的函数，方法是给它们一个输入类型Term F，而函数接受任何输入类型，方法是给它们一个输入类型Term p。

于 2011-09-27T20:15:27.443 回答