0

我需要一个过程，它接受一个列表并检查一个元素是否是该列表的一部分，即使列表包含列表也是如此。到目前为止，我已经写了这个：

(define (element-of-set? element set)
    (cond ((null? set) #f)
    ((eq? element (car set)) #t)
    (else (element-of-set? element (cdr set))))))

但是，如果您有一个如下所示的列表：

(a (a b b (c b) 3) 5 5 (e s) (s e s))

然后我的书面文件element-of-set?不承认 3 是此列表的一部分。我究竟做错了什么？

4

3 回答 3

0

你只需要另一个子句来检查是否car是一个列表。将此添加到您的cond（在eq?子句之后）：

((list? (car set))
 (or (element-of-set? element (car set))
     (element-of-set? element (cdr set))))

这在任何子列表上递归。

于 2013-10-08T15:00:32.850 回答
0

你不会重复car你的set论点。

如果你评价

(element-of-set? 3 '(a (a b b (c b) 3) 5 5 (e s) (s e s)))

根据您当前对 的定义element-of-set?，它会执行类似的操作

  • 检查是否(eq? 3 'a)，没有。
  • 检查是否(eq? 3 '(a b b (c b) 3))，没有。
  • 检查是否(eq? 3 5)，没有
  • 检查是否(eq? 3 5)，没有
  • 检查是否(eq? 3 '(e s))，没有
  • 检查是否(eq? 3 '(s e s))，没有。
  • 我不在列表中；3不是'(a (a b b (c b) 3) 5 5 (e s) (s e s))

如果您想检查深度集成员资格，您需要重新定义您的过程，以便如果该元素本身是car一个. 就像是setlist

...
((list? (car set)) (or (element-of-set? element (car set)) 
                       (element-of-set? element (cdr set))))
...

应该这样做，假设list?实际上是定义的（我在这台机器上没有方案解释器，所以我不确定。你可能需要(not (atom? (car set)))改用）。

于 2013-10-08T14:14:25.067 回答
0

与其根据列表的列表来思考，这可能是一个有用的地方，可以根据由对（也称为 cons 单元）构建的树来思考。cons 单元格是您调用(cons x y)时返回的内容，x称为 its car，y称为 its cdr。当您e在某个对象中搜索元素时object，您可以这样做：

  1. 是e一样的object吗？如果是这样，你已经找到了！
  2. (a) 是object一对吗？如果是，那么检查e是 (b) in itscar还是 (c) in its cdr，如果是，那么你已经找到了！
  3. 否则，你没有找到它，它也无处可寻。

or将其转换为代码相对简单，您甚至可以使用and使其非常干净and：

(define (tree-find e object)
  (or (eq? e object)                           ; 1.
      (and (pair? object)                      ; 2.a
           (or (tree-find e (car object))      ; 2.b
               (tree-find e (cdr object))))))  ; 2.c

现在，这甚至允许您在树中查找树的子部分。例如，如果你取出树'((1 2) (3 (4 5)) (6 7))并提取它的第二个元素（列表(3 (4 5))），并询问它是否是成员，你会得到肯定的答案。请注意，这是有效的，因为您正在检查eq?，因此它只会找到相同的对象，而不仅仅是具有相同结构的对象：

(let* ((l '((1 2) (3 (4 5)) (6 7)))
       (e1 (cadr l))           ; (3 (4 5)), from l
       (e2 (list 3 '(4 5))))   ; (3 (4 5)), but not from l
  (display (tree-find e1 l))   ; #t
  (display (tree-find e2 l)))  ; #f

然而，因为一个正确的列表被一个空列表终止（例如，(1 2 3)is (1 . (2 . (3 . ())))），如果输入中有一个正确的列表，tree-find它将总是说它'()是一个成员。因此，您可能希望明确禁止这种情况：

(define (tree-find e object)
  (or (and (eq? e object)
           (not (null? e)))                   ; check only non-null objects
      (and (pair? object)
           (or (tree-find e (car object))
               (tree-find e (cdr object))))))
于 2013-10-08T14:38:52.470 回答