Найти элемент списка в списках в списке

Question

Мне нужна процедура, которая берет список и проверяет, является ли элемент частью этого списка, даже если список содержит списки. До сих пор, я написал это:

(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 является частью этого списка , Что я делаю не так?

Answer 1

Вы не повторяете 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)), nope.
• проверить, если (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 из set, если этот элемент сам по себе является list. Что-то вроде

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

должны это сделать, если предположить, list? фактически определяется (я не имею схемы переводчика на этой машине, так что я не уверен. Вы, возможно, придется использовать (not (atom? (car set))) вместо этого).

Answer 2

Вместо того, чтобы думать о списках списков, это может быть полезным местом для размышлений в терминах дерева, построенного из пар (также называемого cons-клетками). Ячейка cons - это то, что вы возвращаете, когда звоните (cons x y), и x называется его car, а y называется его cdr. Когда вы ищете для элемента e в каком-то объекте object, вы можете сделать это следующим образом:

1. Is e же, как object? Если это так, вы его нашли!
2. (a) Есть object пара? Если да, то проверьте, является ли e (b) в его car или (c) в его cdr, и если да, то вы его нашли!
3. В противном случае вы не нашли его и его нигде не было.

Это относительно просто перевести в код, и вы даже можете сделать это довольно чистый, используя or и 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) - (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)))))) 

Answer 3

Вам просто нужно другое положение, чтобы проверить, если car список. Добавьте это в cond (после пункта eq?):

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

Это рекурсивно на любых подсписков.