Реализация подсписок? используя накопленный в Racket

Question

Мне нужно реализовать подсписку? как однострочная функция, использующая аккумулирование. Предположим, что true, если set1 находится в set2.

Что-то вроде этого:

(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 применяет бинарный оператор op для всех результатов применения func к элементам списка ls. И поскольку список может быть пустым, в этих случаях функция определена, чтобы вернуть значение base.

Так, например, в предположении, рекурсивное выполнение функции, следующее выражение

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

производит 14, так как это эквивалентно:

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

, что составляет 1 + 4 + 9 + 0.

Чтобы решить вашу проблему, вам необходимо определить вызов accumulate, который применяет тот же оператор к списку элементов и . n объединить результаты. В вашем случае применяемая операция является тестом, если элемент является членом списка (member?), и вы можете применить его ко всем элементам set1. И вы должны знать из определения подмножества, что множество s1 является подмножеством другого множества s2 тогда и только тогда, когда все элементы s1 содержатся в s2. Таким образом, оператор, который должен применяться для объединения всех результатов теста, является только логическим оператором and, так что это будет верно, если все элементы s1 являются членами s2 и false в противном случае. Последнее, что нужно решить, это базовое значение: это должно быть правдой, поскольку пустой набор всегда содержится в другом наборе.

Так что это возможно определение subset?:

(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