I'm trying to write a function that adds an element to each element of a given powerset. No matter what it always evaluates (null pset) as true. I can't understand why.
Here's what I have so far:
(defun addxtopowerset(x pset)
(cond
((null pset) (list x '())) ; If the powerset is null, display x and NIL.
;;First display a list combining x and the first item of pset. Then display the first item of pset itself. Then recursively call the function passing the rest of pset as a parameter.
(T (list 'x (car pset))(list (car pset))
(addxtopowersetch x (cdr pset)))))
First, note that in the terminal case you should return an empty list, since is in the recursion that all the elements of the powerset are processed, and we should assume that a powerset is always a list of list, each of them representing a set (in fact, the powerset of an empty set contains at least one element, the empty set itself).
So, since a powerset is a non-empty list, the task of adding a new element to the powerset can be solved by adding to the result, for each list of the powerset, both the list and a copy of the list with the element added.
In both cases, “add” means: get something and return a new-something, and use the value returned, otherwise, as Rainer Joswig note, “the result go straight into the digital nirvana”. In other words, in the recursive case your function must add the two values, the list and the new list with the element added, to the result of the recursive call. So, here is the function:
(defun addxtopowerset(x pset)
(if (null pset)
nil
(append (list (car pset) (cons x (car pset)))
(addxtopowerset x (cdr pset)))))
Finally, here a couple of alternative ways of defining the function, the first one with the high order function mapcan:
(defun addxtopowerset(x pset)
(mapcan (lambda(y) (list y (cons x y))) pset))
and the second one with a loop:
(defun addxtopowerset(x pset)
(loop for y in pset append (list y (cons x y))))