2

我正在寻找一种使用 Scheme 中的模式进行搜索的方法。就像,如果我有一个搜索模式

'((x likes  y) (y is a hard sport) (x is rich)) 

和输入

'((Mike likes rugby) (Rachel likes tennis) 
  (rugby is a hard sport ) ( tennis is easy)
  (Mike is rich) (Rachel is rich)) 

我应该只得到迈克,因为他是唯一符合所有限制条件的人。

我已经尝试了好几个小时。我一直试图先将 x 绑定到 Mike ,然后在任何地方使用 Mike 而不是 x 。问题是,我不知道我有多少变量,有没有办法做到这一点,或者我的想法完全错误?

4

2 回答 2

4

如果您需要未知数量的变量,请使用关联列表哈希表来存储名称-值绑定,Scheme 提供了处理这两种数据结构的内置过程。

问题描述和所需的匹配类型看起来很像Prolog或类似逻辑编程系统的工作。如果您在使用 Scheme 时遇到困难,请考虑实现统一算法(如 SICP 所示,或使用嵌入在 Scheme 中的逻辑编程系统,例如KANRENminiKANREN。在我们讨论的同时,您还应该查看The Reasoned Schemer以供参考。

于 2013-03-18T18:49:51.093 回答
2

您在这里尝试做的是相当经典的逻辑编程。我一直用于 Scheme 的方法是amb运算符的一些变体。

amb像这样工作:

(let ((x (amb 1 2 3 4))
      (y (amb 5 6 7 8))
   (rule (= 10 (+ x y))
   (list x y))

这将返回一些x y,因此它们的总和为 10。现在使用这个和其他一些巫术,我们可以制作你的系统。

首先,模式将成为我们的“规则”。所以假设我们像这样格式化我们的模式:

'((list-of-vars) (rule 1) (rule 2) (rule 3))

现在对于我们的输入数据,假设它的结构如下:

'((list-of-values) (fact 1) (fact 2) (fact 3))

现在我们的生活变得非常轻松,我们只想让我们的方案宏/程序/巫术做这样的事情:

(define-syntax resolve
  (syntax-rules ()
    [(_ ((v1 vs ...)
         r1 rs ...)
        ((ps ...)
     f1 fs ...))
     (let* ((v1 (amb ps ...))
           (vs (amb ps ...))
           ...
           (sym-table (list (cons (quote v1) v1)
                            (cons (quote vs) vs)
                        ...))
           (facts '(f1 fs ...))
           (rules '(r1 rs ...)))
       (map rule (map
                  (lambda (rule)
                    (member (substitute rule sym-table)
                            facts))
                  rules))
       sym-table)]))

要点中的完整代码

希望这能给你一个起点,让我知道你有什么问题。

于 2013-03-18T17:58:33.780 回答