Scheme에 더 많은 목록을 교차 시킴

Question

Scheme에서 더 많은 목록을 교차 시키려고하고 있는데 약간의 도움이 필요합니다. 목록은 다음과 같이 :

처음 두 :

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

및

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

내가 (예를 들어 A) 첫 번째 목록에서와 참조하십시오있을 경우 모든 목록에서 볼 필요가 A와 B의 공통점이 적어도 하나가되도록 두 번째 목록에 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) (?game air-hockey)) 공통점 (?x john)이 때문에 내 새로운 결과 목록 첫 번째 목록에있는 것 :

이제 결과 목록은 다음 목록을 교차해야합니다 다음과 같이 보입니다 : ((?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))) 

이 공통으로 적어도 하나 개의 요소가 매 2 개 목록을 위해 내가 그들의 재회를해야하고 있다는 것을 의미 새로운 결과 목록에 추가하십시오.

이제 제 질문은 Scheme에서 구현할 때 약간의 도움이 필요합니까? 나는 코드를 사용하지 않고 어떤 기능을 사용해야하는지에 대한 몇 가지 아이디어 만 갖고 싶다. :)

Answer 1

, 나는 '그것 때문에리스트의 구현을 쓰지 않습니다 작업에있어 최상의 데이터 구조는 아니므로 라켓의 설정 작업 측면에서 문제를 해결하는 방법을 보여주기 때문에 목록을 사용하도록 변환 할 수 있습니다.첫째, 데이터의 표현 : 장소의 표현으로

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

을 peatedly는 다른 데이터 세트를 하나 개의 데이터 세트의 모든 요소를 ​​일치 여러 데이터 집합 사이에서 연속적인 일치를 찾으려면 각 데이터 집합과 함께 필요한만큼 여러 번 호출하여 결과를 누적하면됩니다.

마지막으로 알 수 있듯이 최종 결과는 예상 한 것입니다.

Answer 2

설명을 개선하는 것으로 시작하겠습니다. (?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