how to test whether one list is a member of another

Question

Lets say I have two lists, ((1 2 3)) and (((1 2 3)) ((4 5))). I want to be able to tell if the first list is a member of the second list. I have tried to use subsetp, but it does not return true for this query. How can I accomplish this?

Answer 1

As Rainer Joswig mentioned in the comments, you're not checking for subsets, but for members, which you can do using the aptly named member function. Member returns a generalized boolean, i.e., nil for false, and something, not necessarily t, non-nil for true. Specifically, if an element is a member of the list, member returns the tail of the list whose first element is the element.

CL-USER> (member 3 '(1 2 3 4 5))
(3 4 5)
CL-USER> (member 7 '(1 2 3 4 5))
NIL

Of course, when checking membership in a list, there's a question of how to compare the given item with the elements of the list. Member's default comparison is eql, which works on things like numbers, as shown in the example above. For your case, however, you probably want to test with equal, since ((1 2 3)) might not be the same object as the first element of (((1 2 3)) ((4 5))):

CL-USER> (member '((1 2 3)) '(((1 2 3)) ((4 5))))
NIL
CL-USER> (member '((1 2 3)) '(((1 2 3)) ((4 5))) :test 'equal)
(((1 2 3)) ((4 5)))
CL-USER> (member '((4 5)) '(((1 2 3)) ((4 5))) :test 'equal)
(((4 5)))
CL-USER> (member '((1 2 4)) '(((1 2 3)) ((4 5))) :test 'equal)
NIL

Answer 2

If you want to have lists as elements of your sets for subsetp, you have to change the value of the :test keyword.

CL-USER 1 > (subsetp '(1 2 3) '(1 2 3 4 5))
T
CL-USER 2 > (subsetp '((1) (2) (3)) '((1) (2) (3) (4) (5)))
NIL

The first one gives T, the second one gives NIL. Why? Because equality is checked with #'eql which works for identical objects or numbers of the same value and of same type. Since two lists must not be identical objects, (eql '(1) '(1)) gives NIL. (That may depend on your CL implementation.) If you want to compare a tree of conses, tree-equal can help you.

CL-USER 3 > (subsetp '((1) (2) (3)) '((1) (2) (3) (4) (5)) :test #'tree-equal)
T

I don't understand the structure of the sets you gave as example completely, but I hope this helps.