list - 方案:找出 "complex"元素是否在 "complex"列表中

Question

我正在使用 R5RS 标准的 Scheme 实现。

现在假设您必须找出一个元素 '(2 3 4) 是否在列表 '(1 2 3 4) 中。

至于示例，更严格地说，您希望:

1. (is-in? '(2 3 4) '(1 2 3 4)) -> #f
2. (is-in? '(2 3 4) '(1 (2 3 4)) -> #t

问题:如何获得示例 1 中的那种行为？

让我解释一下:当您搜索一个列表时，您可以使用 car 或 cdr 来获取它的零件。现在，如果你递归地遍历列表，你最终会得到:

3. (cdr '(1 2 3 4)) -> '(2 3 4)
4. (cdr '(1 (2 3 4)) -> '((2 3 4))

所以最终，我们得到了 2 个列表。您可以在这里看到，子列表 '(2 3 4) 包含在 3 和 4 的两个结果中。

请看3和4与1和2的矛盾:虽然'(2 3 4)不包含在'(1 2 3 4)中，但cdr的递归调用返回'(2 3 4)，这is 等于 '(2 3 4) - 并使用 equal? 函数，在递归调用中的某处，我们最终得到 1 和 2 的 #t:

5. (is-in? '(2 3 4) '(1 2 3 4)) -> #t
6. (is-in? '(2 3 4) '(1 (2 3 4)) -> #t

那么如何从 1 获得那种行为呢？我想要一个函数，它适用于所有不同类型的数据。这是我的函数，它像 5 和 6 一样工作(throught 应该像 1 和 2 一样工作):

(define or (lambda (x y)
             (cond ((eq? x y) (eq? x #t))
                   (#t #t)
                   )
             )
  )

(define and (lambda (x y)
              (cond ((eq? x y) (eq? x #t))
                    (#t #f)
                    )
              )
  )

(define atom? (lambda (x)
                (not (pair? x))
                )
  )

(define length (lambda (x)
                       (cond ((eq? x '()) 0)
                             ((atom? x) 1)
                             (#t (+ (length (car x)) (length (cdr x))))
                             )
                       )
  )

(define equal? (lambda (x y)
                 (cond ((and (atom? x) (atom? y)) (eq? x y))
                       ((not (eq? (length x) (length y))) #f)
                       ((not (and (pair? x) (pair? y))) #f)
                       (#t (and (equal? (car x) (car y)) (equal? (cdr x) (cdr y))))
                       )
                 )
  )

(define is-in? (lambda (x y)
                 (cond ((equal? x y) #t)
                       (#t (cond ((pair? y) (or (is-in? x (car y)) (cond ((eq? (length y) 1) #f)
                                                                          (#t (is-in? x (cdr y)))
                                                                          )))
                                 (#t #f)
                                 )
                           )
                       )
                 )
  )

更新:

我想要的是有一个general 函数，它可以告诉您某个object 是否在另一个object 中。我将实体命名为 object 以强调该函数应该适用于任何输入值，无论是简单的还是复杂的。

示例用法:

1. (is-in? 1 '(1 2 3)) ;-> #t
2. (is-in? '(1) '(1 2 3)) ;-> #f
3. (is-in? '(2 . 3) '(1 2 . 3)) ;-> #f
4. (is-in? '(2 . 3) '(1 (2 . 3))) ;-> #t
5. (is-in? '2 '(1 2 . 3)) ;-> #t
6. (is-in? '(2) '(1 2 . 3)) ;-> #f
7. (is-in? '(1 2 (3 4 (5 6 . (7 . 8)) 9) 10 11 (12 . 13)) '(1 (2 3 ((4 ((6 (3 . ((1 2 (3 4 (5 6 . (7 . 8)) 9) 10 11 (12 . 13)))) 3) 4)) 5) 2))) ;-> #t
8. (is-in? '(2 3 4) '((1 (2 3 4)) (1 2 3 4))) ;-> #t
9. (is-in? '(2 3 4) '(1 2 3 4)) ;-> #f
10. (is-in? '(2 3 4) '(1 (2 3 4))) ;-> #t
11. (is-in? '(1) '(1)) ;-> #t

Answer 1

首先 - 为什么要重新定义 and、or、equal? 和 length？这些是内置原语。还有你对atom?的定义是错误的，应该是:

(define (atom? x)
  (and (not (pair? x))
       (not (null? x))))

我猜你需要从头开始实现这个作为家庭作业的一部分。让我们看看这是如何实现的，填空以获得您的答案:

(define (is-in? ele lst)
  (or <???>                          ; trivial case: ele == list
      (member? ele lst)))            ; call helper procedure

(define (member? ele lst)
  (cond ((null? lst)                 ; if the list is empty
         <???>)                      ; then the element is not in the list
        ((atom? lst)                 ; if the list is not well-formed
         (equal? <???> <???>))       ; then test if ele == list
        (else                        ; otherwise
         (or (equal?  ele <???>)     ; test if ele == the 1st element in the list
             (member? ele <???>)     ; advance the recursion over the `car`
             (member? ele <???>))))) ; advance the recursion over the `cdr`

请注意 member? 中的第二种情况是必需的，因为在给出的示例中存在格式错误的列表(以非空值结尾)。上述解决方案将正确处理问题中提供的所有示例。