2

我正在尝试与 Scheme 中的更多列表相交，我需要一些帮助。列表如下所示：

前两个：

(((?x john) (?city new-york))  
 ((?x mike) (?city chicago))  
 ((?x mary) (?city london)))

和

(((?city chicago))     
 ((?city new-york)))

我需要查看第一个列表中的每个列表（比如 A），看看第二个列表中是否有一个列表（比如 B），以便 A 至少有一个与 B 相同的元素。如果没有这样的元素，结果列表将不包含 A。上述两个列表的结果将是：

(((?x john) (?city new-york))  
 ((?x mike) (?city chicago)))

因为该列表((?x mary) (?city london))与来自(((?city chicago) ((?city new-york))).

现在结果列表必须与下一个列表相交：

(((?x mike) (?game tennis))  
 ((?x john) (?game air-hockey)))

结果列表中的第一个列表((?x john) (?city new-york))将与我的新结果列表中的第一个列表(?x john)相同((?x john) (?game air-hockey))，因此在我的新结果列表中，第一个列表将如下所示((?x john) (?city new-york) (?game air-hockey))：按照第二个列表的这种模式，我将得到((?x mike) (?city chicago) (?game tennis))，我的新结果列表将是：

(((?x john) (?city new-york) (?game air-hockey))  
 ((?x mike) (?city chicago) (?game tennis)))

这意味着，对于每两个至少有一个共同元素的列表，我必须重新组合并将其添加到新的结果列表中。

现在我的问题是，你能帮我在 Scheme 中实现这个吗？我不想要代码，只想要一些关于我应该使用哪些功能的想法:)。

4

2 回答 2

2

我知道你必须用列表来解决这个问题，我不会写一个列表实现，因为它会很麻烦（它不是工作的最佳数据结构），相反我会告诉你如何解决这个问题Racket 的集合操作，因此您可以将其转换为使用列表。首先，数据的表示：

(define s1 (set (set '(?x john) '(?city new-york))
                (set '(?x mike) '(?city chicago))
                (set '(?x mary) '(?city london))))

(define s2 (set (set '(?city chicago))
                (set '(?city new-york))))

(define s3 (set (set '(?x mike) '(?game tennis))
                (set '(?x john) '(?game air-hockey))))

有了表示，我们需要一个给定单个数据的过程，如果它与数据列表共享某些元素，它会找到一个匹配项，如果它没有找到任何匹配项，它会返回数据的并集返回#f：

(define (find-match one-set set-of-sets)
  (cond ((set-empty? set-of-sets)
         #f)
        ((not (set-empty? (set-intersect one-set (set-first set-of-sets))))
         (set-union one-set (set-first set-of-sets)))
        (else
         (find-match one-set (set-rest set-of-sets)))))

例如：

(find-match (set '(?x mike) '(?city chicago))
            (set (set '(?x mike) '(?game tennis))
                 (set '(?x john) '(?game air-hockey))))

=> (set '(?x mike) '(?city chicago) '(?game tennis))

现在很容易编写一个重复匹配一组数据中的所有元素与另一组数据的过程：

(define (join s1 s2)
  (let loop ((s1 s1)
             (result (set)))
    (if (set-empty? s1)
        result
        (let ((match (find-match (set-first s1) s2)))
          (if match
              (loop (set-rest s1) (set-add result match))
              (loop (set-rest s1) result))))))

例如，s1和s2（如上定义）之间的第一个匹配项如下所示：

(join s1 s2)

=> (set (set '(?x mike) '(?city chicago))
        (set '(?x john) '(?city new-york)))

要在多组数据中查找连续匹配，只需join根据需要多次调用，每组数据累积结果：

(define (join-all . data)
  (if (empty? data)
      (set)
      (foldr join (first data) (rest data))))

(join-all s1 s2 s3) ; equivalent to (join (join s1 s2) s3)

=> (set
     (set '(?x john) '(?city new-york) '(?game air-hockey))
     (set '(?x mike) '(?city chicago)  '(?game tennis)))

如您所见，最终结果是我们预期的结果。

于 2013-04-06T14:26:04.523 回答
0

我将从改善您的描述开始。(?x john)不是一个list它是一个query。并且((?x john) (?city new-york))不是列表列表，它是proposition（？？）。和

(((?x john) (?city new-york))  
 ((?x mike) (?city chicago))  
 ((?x mary) (?city london)))

不是列表列表的列表，它是一个set of propositions.

一旦你开始明确地描述事物，你就可以开始在实体上定义一些操作：

query_match
query_has_variable
proposition_has_query
proposition_extend
etc
于 2013-04-06T14:22:51.687 回答