list - 如何编写 “set-equal?” 谓词？

Question

我如何构建一个 same? 谓词返回 #t 和 (same? '(4 6) '(6 4))? 我一直坚持编写一个 (same? a b) 谓词，如果 a 和 b 返回 #t是相等的集合，否则 #f。还有一个类似的谓词 (element? el set) 确定 el 是否是 set 的元素。

(是的，这是家庭作业，所以我不是在寻求一个完全完成的解决方案。我只需要在正确的方向上得到一个或几个碰撞，因为我们的老师几乎没有帮助.)

我们使用列表来表示集合。我们被要求自己构建我们需要的一切。 map 等高阶函数几乎被禁止。

问题是我的元素？和一样？不适用于:

(same? '(4 6) '(6 4))<br/>
(element? '(2 3) '(1 8 5 '(3 2) 4))

这些应该返回 #t，但他们没有，我明白为什么，但我仍然无法修复它。

我的 element? 看起来像这样，我知道它只适用于相同顺序的列表，但问题是我如何改进它？ (setEmpty、setFirst、setRest 定义为 null?、car 和 cdr。出于某种原因，我们被要求制作自己的。)

(define element?
  (lambda (x set)
     (cond ((setEmpty? set) #f)
      ((equal? x (setFirst set)) #t)
      (else (element? x (setRest set)))
      )
   )
)

我有一个有效的 set?-predicate 看起来像这样，可能有用:

(define set?
  (lambda (set)
    (cond ((setEmpty? set) #t)
          ((list? (setFirst set))
            (if (element? (setFirst set) (setRest set))
             #f
             (set? (setFirst set))))
          (else (if (element? (setFirst set) (setRest set))
                #f
                (set? (setRest set))
                )
            )
        )
     )
 )

如果列表及其“子列表”没有重复项，则返回 #t。我还有一个程序可以从一个列表中创建一个真正的集合，该列表可以正常工作。

Answer 1

一些提示，让您朝着正确的方向前进。

element? 过程大部分是正确的，除了它不应该使用 equal? 进行键比较 - 它应该使用 same?, 和 same? 应该区分两种情况:比较的元素是原子还是集合。

因此不难想象，整个练习的正确性取决于same?的实现。而这又取决于所选择的集合表示。关于 representing sets 有一整章在精彩的 SICP 书中(包括将集合表示为列表)，您应该从阅读它开始，以了解您的方位。

一旦您实现了集合的原始过程，就很容易检查两个集合是否相等，我将留给您实现 setSize 和 setUnion:

(= (setSize a) (setSize b) (setSize (setUnion a b)))

或者，正如@sds 在他的回答中指出的那样，如果两个集合是彼此的子集，您可以确定它们是否相同 - 并且您应该在您的拥有:

(and (subset? a b) (subset? b a))