하위 목록 구현 중입니까? 라켓에 누적 사용

Question

하위 목록을 구현해야합니까? 누적을 사용하는 한 줄짜리 함수로 set1이 set2에 있으면 true를 반환한다고 가정합니다. 이 같은

뭔가 :

(define subset? 
    (lambda (set1 set2) 
    (accumulate member? (car set1) (lambda (x) x) set2))) 

는 솔직히 내가 축적이 멤버 작업을 가정하는 방법에 단지 혼란 스러워요 생각, 또는 회원이 연산자도 올바른 선택 인 경우.

내 축적 기능은 다음과 같습니다

(define accumulate 
    (lambda (op base func ls) 
    (if (null? ls) 
     base 
     (op (func (car ls)) 
     (accumulate op base func (cdr ls)))))) 

및 멤버?

(define member? 
    (lambda (item ls) 
    (cond ((null? ls) #f) 
     ((equal? item (car ls)) #t) 
     (else (member? item (cdr ls)))))) 

Answer 1

이 subset?의 정확한 정의는 먼저 우리가 이해해야합니다 제공하는 방법에 기능 accumulate 작품과 매개 변수의 의미. 우리는 재귀 정의를 "전개"경우

, 우리 accumulate ls리스트의 요소에 적용 func 모든 결과 이진 연산자 op 적용 것을 알 수있다. 목록이 비어있을 수 있기 때문에이 경우 함수는 base 값을 돌려주기 위해 정의됩니다.

그래서, 예시, 함수의 재귀 실행을 가정

(accumulate + 0 sqr '(1 2 3)) 

14 생산은 다음 식 것은 등가이므로 1 + 4 + 9이다

(+ (sqr 1) (+ (sqr 2) (+ (sqr 3) 0))) 

+ 0

문제를 해결하려면 동일한 연산자를 요소 목록에 적용한 accumulate에 대한 호출을 정의해야하고 n 결과를 결합하십시오. 위의 경우, 적용 할 작업은 요소가 목록의 구성원 (member?) 인 경우 테스트이며, set1의 모든 요소에 적용 할 수 있습니다. 그리고 s1의 모든 원소가 s2에 포함되어있는 경우에만 집합 s1이 다른 집합 s2의 하위 집합이라는 것을 부분 집합의 정의에서 알 수 있습니다. 따라서 모든 테스트 결과를 결합하기 위해 적용해야하는 연산자는 and 부울 연산자이므로 모두 인 경우 s1의 요소는 s2의 멤버이고 그렇지 않으면 false가됩니다. 마지막으로 결정할 것은 기본 값입니다. 빈 세트가 항상 다른 세트에 포함되므로이 값은 참이어야합니다.

(define (subset? set1 set2) 
    (accumulate 
    (lambda (x y) (and x y))  ;; the combination operator 
    #t       ;; the value for the empty list 
    (lambda(x) (member x set2)) ;; the function to be applied to all the elements of 
    set1))      ;; the set set1