Intersect more lists in Scheme

问题:

I am trying to intersect more lists in Scheme and I need a little help. The lists look like this:

The first two:

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

and

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

I need to look in every list (say A) from the first list and see if there is a list (say B) in the second one so that A has at least one element in common with B. If there is no such element, the resulting list will not contain A. The result for the two lists mentioned above will be:

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

since the list ((?x mary) (?city london)) has nothing in common with any list from (((?city chicago) ((?city new-york))).

Now the resulting list has to be intersected with the next list:

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

The first list from the resulting list, ((?x john) (?city new-york)) will have (?x john) in common with ((?x john) (?game air-hockey)) and therefore in my new resulting list the first list will look like this: ((?x john) (?city new-york) (?game air-hockey)). Following this pattern with the second list, I will get ((?x mike) (?city chicago) (?game tennis)) and my new resulting list will be:

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

This means that, for every two lists that have at least one element in common I have to do their reunion and add it to the new resulting list.

Now my question is, can you give me a little help in implementing this in Scheme? I don't want the code, only some ideas regarding which functions should I use :).

回答1:

I understand that you have to solve this with lists, I won't write a list implementation because it'd be cumbersome (it's not the best data structure for the job), instead I'll show you how to solve the problem in terms of Racket's set operations, so you can translate it to use lists. First, a representation of the data:

(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))))

With the representation in place, we need a procedure that given a single datum finds if it shares some element in common with a list of data - if it finds one match, it returns the union of data, if it doesn't find any it returns #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)))))

For example:

(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))

Now it's easy to write a procedure that repeatedly matches all elements in one set of data with another set of data:

(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))))))

For instance, the first match between s1 and s2 (as defined above) would look like this:

(join s1 s2)

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

To find successive matches among several sets of data just call join as many times as needed, with each set of data, accumulating the result:

(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)))

As you can see, the end result is the one we expected.

回答2:

I'd start by improving your description. (?x john) is not a list it is a query. And ((?x john) (?city new-york)) is not a list of lists it is a proposition (??). And

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

is not a list of list of lists it is a set of propositions.

Once you start describing things unambiguously you can then start defining some operations on the entities:

query_match
query_has_variable
proposition_has_query
proposition_extend
etc