实现子列表？在 Racket 中使用 accumulate

Question

我需要实现子列表？作为使用 accumulate 的单行函数。如果 set1 在 set2 中，则假设 return 为真。

像这样：

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

老实说，我只是对 accumulate 如何与 member 一起工作感到困惑，或者 member 是否是运算符的正确选择。

我的累积函数是：

(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 的调用，将相同的运算符应用于元素列表，然后然后组合结果。在您的情况下，要应用的操作是测试元素是否是列表 (member?) 的成员，并且您可以将其应用于 set1 的所有元素。你应该知道，从子集的定义来看，一个集合s1是另一个集合s2的子集当且仅当s1的所有元素都包含在s2中。因此，必须应用于组合所有测试结果的运算符只是 and 布尔运算符，因此如果 all s1 的元素是成员，则它将为真s2 否则为假。最后要决定的是基值：这应该是真的，因为一个空集总是包含在另一个集中。

所以这是 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

实现子列表？在 Racket 中使用 accumulate

Implementing sublist? using accumulate in Racket

scheme

racket

member

sublist

accumulate