2

我正在开发一个反向链接引擎作为学校项目。到目前为止，我主要是用 C 语言完成项目，所以我决定为那个项目尝试 Haskell。我阅读 LYAH 是为了开始并开始在我的推理引擎中实现规则和事实的表示。到目前为止，这就是我得到的

module Inference () where

type Op = Bool -> Bool -> Bool
type Label = String
type Fact = (Label, [Rule])
data Rule = Operation Rule Op Rule
          | Fact Fact

eval_fact:: [Label] -> Fact -> Bool
eval_fact proved (label,rules) = label `elem` proved || any (eval_rule proved) rules

eval_rule:: [Label] -> Rule -> Bool
eval_rule proved (Fact x) = eval_fact proved x
eval_rule proved (Operation r op r') =  eval_rule proved r `op` eval_rule proved r'

这个想法是要有某种图表，其中事实节点指向规则节点，除非事实已经在已知事实的列表中。

但是，在这里我遇到了定义我的实际事实和规则的问题。

做类似的事情

let fact_e = ("E", [Fact ("C", [(Operation (Fact ("A", [])) (||) (Fact ("B", [])))])])

在 ghci 中以表示规则

C => E
A || B => C

这样可行。但是我真的不知道以编程方式构建这些规则的方向。此外，我看不到如何使用该方案处理循环规则（E => A例如添加规则）。

我已经看到有一些方法可以在 Haskell 中定义自引用数据结构，在 Haskell wiki 上使用名为“Tying the knot”的技巧，但我不知道如何（或什至）在当前情况下应用它。

我的问题本质上是，我是朝着正确的方向前进，还是用这种方法完全倒退了？

PS：在我看来，我的代码并不像它应该的那样简洁（传递 [Label] 列表，重复eVal_rule proved很多次......），但我也不知道如何以另一种方式做到这一点.

4

1 回答 1

2

这个想法是首先将规则解析为非自引用的中间表示。例如，给定表示：

type Program = [(Label, [Rule_P])]
data Rule_P = Operation_P Rule_P Op Rule_P | Fact_P Label

然后是一组规则：

C => E
A || B => C
E => A
F => E

将被解析，由蕴含目标收集，并表示为：

prog1 :: Program
prog1 = [ ("E", [ Fact_P "C"                                       -- C => E
                , Fact_P "F" ])                                    -- F => E
        , ("C", [ Operation_P (Fact_P "A") (||) (Fact_P "B") ])    -- A || B => C
        , ("A", [ Fact_P "E" ]) ]                                  -- E => A

然后，将其转换为循环自引用知识库（使用您的原始Fact类型）：

type Knowledge = [Fact]

你像这样打结：

learn :: Program -> Knowledge
learn program = knowledge

  where

    knowledge :: [Fact]
    knowledge = [ (target, map learn1 rules_p) | (target, rules_p) <- program ]

    remember lbl = fromJust (find ((==lbl) . fst) knowledge)

    learn1 :: Rule_P -> Rule
    learn1 (Fact_P lbl) = Fact (remember lbl)
    learn1 (Operation_P rule1 op rule2) = Operation (learn1 rule1) op (learn1 rule2)

这也许值得一些解释。我们knowledge通过简单地应用将原始程序中learn1每次出现的非自引用转换为知识库中的自引用来创建。该函数以明显的递归方式执行此操作，并且它通过查找（ ing）我们正在定义的主体中的标签来“打结” 。Rule_PRulelearn1Fact_Prememberknowledge

无论如何，为了向自己证明它是自我参照的，你可以在 GHCi 中使用它：

> know1 = learn prog1
> Just [Operation factA _ _] = lookup "C" know1
> Fact ("A", [factE]) = factA
> Fact ("E", [factC, _]) = factE
> Fact ("C", [Operation factA' _ _]) = factC
> Fact ("A", [factE']) = factA'

当然，尝试：

> eval_fact [] $ fromJust $ find ((=="E").fst) (learn prog1)

将循环直到它耗尽内存，因为它试图（不成功地）从 E 中的 A 中从 C 中证明 E 等等，因此您需要添加一些逻辑来中止循环证明。

于 2019-06-22T16:19:19.343 回答