3

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

（是的，这是家庭作业，所以我不是在寻求完全完成的解决方案。我只需要在正确的方向上获得一个或几个凹凸，因为我们的老师几乎找不到任何帮助。）

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

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

(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?看起来像这样的工作谓词，可能有用：

(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如果列表及其“子列表”没有重复项，则返回。我还有一个程序可以从一个列表中创建一个真正的集合，其中的重复项可以正常工作。

4

4 回答 4

2

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

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

所以不难想象，整个练习的正确性取决于same?. 而这又取决于选择的集合表示。精彩的 SICP 书中有一整章是关于表示集合的（包括将集合表示为列表），你应该从阅读它开始，以了解你的方向。

一旦你实现了集合的原始过程，就很容易检查两个集合是否相等，我将把它留给你来setSize实现setUnion：

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

或者，正如@sds 在他的回答中指出的那样，如果两个集合是彼此的子集，您可以确定它们是否相同 - 您应该subset?自己实现该过程：

(and (subset? a b) (subset? b a))
于 2013-10-06T18:48:54.917 回答
1

球拍程序员的注意事项：如果可以，请避免重新发明轮子。如果合适，请使用标准库的racket/set，它提供了良好的集合实现。

于 2013-10-08T18:54:30.767 回答
1

您的问题似乎是您正在使用equal?来比较element?.

您需要编写自己的element-equal?，这将考虑到 set 元素可能是列表而不是原子，并使用它而不是equal?.

至于same?- 我认为这样实现它是最容易的：

(define same? 
  (lambda (a b) 
    (and (subset? a b)
         (subset? b a))))

和

(define subset? 
  (lambda (a b)
    (or (isEmpty a)
        (and (element? (first a) b) 
             (subset? (rest a) b)))))
于 2013-10-06T18:47:49.243 回答
0

我的实验室现在实际上运行得很顺利。我要感谢所有发表评论的人，并向其他在同一种实施中苦苦挣扎的人提及一些事情。

从我的角度来看的指针： - 抽象地思考。阅读关于集合论的快速介绍。足以知道集合、子集、空集、联合等的定义。

- 在一张纸上写下所有的程序，想想什么程序需要什么其他程序。

- 当考虑如何写相同的？例如，假设您有一个已经可以工作的过程子集。事实上，你已经有很多有效的程序了，（即使你还没有它们=））别担心，试着想想哪些程序是一样的？将需要使其尽可能整洁。继续这样处理您的所有程序。

- 您可能会遇到程序问题，只是在它们之间来回发送东西，并且您的程序进入无限循环。如果您从一开始就很小心，并认识到何时会出现这种问题，那么您就不应该遇到这种情况。但有时你必须重新考虑一些程序。也许他们可以使用其他程序来完成同样的事情？

我还将分享一些程序，看看你的想法。随意屠宰他们，他们工作至今=）..无论如何，这周五就要到期了。附言。我的 proc makeSet 基本上按照听起来的方式进行。它删除所有“级别”中的所有重复元素。

;;; predicate that returns #t if a list is a set and #f otherwise
(define set?
  (lambda (set)
    (cond ((setEmpty? set) #t)
      ((not (list? set)) #f)
      ((equal? (makeSet set) set) #t)
      (else #f))
  )
)

;;; diff returns the difference between set1 and set2
(define diff
  (lambda (set1 set2)
    (cond ((null? set1) '())
       ((null? set2) set1)
       ((not (member? (car set1) set2))
        (cons (car set1) (diff (cdr set1) set2)))
       (else (diff (cdr set1) set2)))
  )
)

哦，我还没有将所有的汽车、cdr 和 cons 更改为我们的“抽象”等于 setFirst 等，我会的。此外，我可能会让 diff 返回其返回值的“makeSet-version”，以确保我总是得到一个集合作为返回。

再次感谢大家！/rem

于 2013-10-16T18:06:04.163 回答