Find an element of list in lists in list

Question

I need a procedure which takes a list and checks if an element is part of that list even when the list contains lists. So far, I've written this:

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

But, if you have a list that looks like this:

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

then my written element-of-set? does not recognize that 3 is a part of this list. What am I doing wrong?

Answer 1

Rather than thinking in terms of lists of lists, this may be a useful place to think in terms of a tree built from pairs (also known as cons cells). A cons cell is what you get back when you call (cons x y), and x is called its car, and y is called its cdr. When you're searching for an element e in some object object, you can do it this way:

1. Is e the same as object? If so, you've found it!
2. (a) Is object a pair? If so, then check whether e is (b) in its car or (c) in its cdr, and if so, then you've found it!
3. Otherwise, you haven't found it, and it's nowhere to be found.

This is relatively straightforward to translate into code, and you can even make it pretty clean using 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

Now, this even allows you to find subparts of a tree within a tree. For instance, if you took the tree '((1 2) (3 (4 5)) (6 7)) and extracted its second element (the list (3 (4 5))), and ask whether its a member, you'll get an affirmative answer. Note that this works because you're checking with eq?, so it would only find the same object, not just one with the same structure:

(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

However, because a proper list is terminated by an empty list (e.g., (1 2 3) is (1 . (2 . (3 . ())))), tree-find will always say that '() is a member if there's a proper list in the input. As such, you might want to explicitly disallow that case:

(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 2

You're not recurring down the car of your set argument.

If you evaluate

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

with your current definition of element-of-set?, it'll do something like

• check if (eq? 3 'a), nope.
• check if (eq? 3 '(a b b (c b) 3)), nope.
• check if (eq? 3 5), nope
• check if (eq? 3 5), nope
• check if (eq? 3 '(e s)), nope
• check if (eq? 3 '(s e s)), nope.
• I'm out of list; 3 is not a member of '(a (a b b (c b) 3) 5 5 (e s) (s e s))

If you want to check for deep set membership, you need to redefine your procedure so that it recurs into the car of set if that element is itself a list. Something like

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

should do it, assuming list? is actually defined (I don't have a scheme interpreter on this machine, so I'm not sure. You may need to use (not (atom? (car set))) instead).

Answer 3

You just need another clause to check if the car is a list. Add this to your cond (after the eq? clause):

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

This recurses on any sublists.