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

このソリューションでは、（で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]

この最後の解決策では、以前と同じように用語を2つの異なるタイプに分割しましたが、今回は、基本的にと同じセマンティクスでコンストラクターをEither Term Predicate追加することを避けています。StructTermPredicate

これは、用語に2つの述語コンストラクターを使用するソリューション1と同じです。1つは再帰対応でStructあり、もう1つPredicateは述語と通常の用語を区別できるようにすることです。

この試行の問題は、Structとが構造的に同等であり、ほぼ同じ意味を持つことですが、たとえば、onと。Predicateの両方で機能する関数を記述できません。(Predicate "p" [])(Struct "p" [])

繰り返しになりますが、私の質問は次のとおりです。述語と用語を次のようにエンコードするためのより良い方法はありますか。

  1. 型アノテーションの述語と用語を区別することができます。
  2. のようなネストされた述語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

これが1つの方法です（おそらく問題の価値はありません）：

{-# 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 に答える