Reputation: 163
I need a function that can check if a list a
is a proper subset of a list b
. My code so far is:
(defun proper-subset (a b)
(cond
(( or (null b)(null b)) nil)
((equal a b) nil)
((find (car a) b) (proper-subset (cdr a) b))
)
)
find
checks that each element of a
is in b
. I know the null arguments need some work as well, but I am trying to figure out how to determine when every element of a
is found in b
and b
has another element. There are built in functions that can make this a lot easier however this a homework question so I have to write my own. Any hints or suggestions would be greatly appreciated.
Upvotes: 0
Views: 1859
Reputation:
The below only adds if
to the set of operations you mention, but this is really an atrocious way to do it. If that's what they teach you (you didn't volunteer for it). It's about time you get some good book on Lisp and study it yourself. This exercise is really pointless in my opinion.
(defun purge (element from-list)
(if (null from-list) nil
(if (equal element (car from-list))
(purge element (cdr from-list))
(cons (car from-list) (purge element (cdr from-list))))))
(defun proper-subset-p (suspect of)
(if (null suspect) (not (null of))
(if (not (equal (purge (car suspect) of) of))
(proper-subset-p
(purge (car suspect) suspect)
(purge (car suspect) of)) nil)))
Same thing, but with cond
(defun purge (element from-list)
(cond
((null from-list) nil)
((equal element (car from-list)) (purge element (cdr from-list)))
(t (cons (car from-list) (purge element (cdr from-list))))))
(defun proper-subset-p (suspect of)
(cond
((null suspect) (not (null of)))
((not (equal (purge (car suspect) of) of))
(proper-subset-p (purge (car suspect) suspect) (purge (car suspect) of)))
(t nil)))
Upvotes: 0
Reputation: 85843
Common Lisp defines a number of functions for working with lists as sets, so you don't need to write your own. In particular, the useful functions appear at the bottom of The Conses Dictionary. The particularly useful ones are
subsetp
almost does what you want, but it's checking for non-proper subsets. However, observe that you can use these functions to compute what you need. The most direct way would be to check if A is a subset of B, and whether B - A ≠ {}. This matches your description, "every element of a is found in b and b has another element".
(defun proper-subsetp (a b)
(and (subsetp a b) ; every element of a is found in b
(not (endp (set-difference b a))))) ; b has another element
CL-USER> (proper-subsetp '(1 2 3) '(1 2 3 4))
T
CL-USER> (proper-subsetp '(1 2 3 4) '(1 2 3 4))
NIL
Since these functions actually take some parameters that let you determine how elements are compared. You can add these in by using an &rest
argument and apply:
(defun proper-subsetp (a b &rest keys)
(and (apply 'subsetp a b keys )
(not (endp (apply 'set-difference b a keys)))))
Using this, you could, rather than comparing the elements directly, compare their lengths:
CL-USER> (proper-subsetp '("a" "bb" "ccc") '("1" "22" "333") :key 'length)
NIL
CL-USER> (proper-subsetp '("a" "bb" "ccc") '("1" "22" "333" "4444") :key 'length)
T
Upvotes: 3