list - 在方案中交叉更多列表

Question

我正在尝试在方案中交叉更多列表，我需要一些帮助。这些列表如下所示:

前两个:

(((?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 ) (?游戏空气曲棍球))。按照第二个列表的模式，我将得到 ((?x mike) (?city Chicago) (?game Tennis)) ，我的新结果列表将是:

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

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

现在我的问题是，你能为我在Scheme中实现这一点提供一些帮助吗？我不需要代码，只想要一些关于我应该使用哪些函数的想法:)。

Answer 1

我知道你必须用列表来解决这个问题，我不会编写列表实现，因为它很麻烦(它不是这项工作的最佳数据结构)，相反，我将向你展示如何解决这个问题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)))

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