Alternative to mapcar lisp

Question

I need to write a recursive function for powerset, but I can't use mapcar, loop.

This is my code so far:

(defun parts (L)
  (cond 
    ((null L)'(nil))    
    (T
      (let ((PXs (parts (cdr L))))
        (append PXs (add(car L) PXs))
      )
    )   
  )
)

(defun add (E Cs)
  (cond
    (
    (null (cdr Cs))
        (list(cons E Cs))
    )
    (T 
        (append(list(cons E (list (car Cs)))) (addE (cdr Cs)))          
    )   
  )
)

But the result for (parts ('1 2 3)) is:

(NIL (3 NIL) (2 NIL) (2 (3 NIL)) (1 NIL) (1 (3 NIL)) (1 (2 NIL)) (1 (2 (3 NIL))))

I found this method

(defun powerset (list)
   (let ((x (car list)))
     (if x
       (let ((p (powerset (cdr list))))
         (append p (mapcar (lambda (list) (cons x list)) p)))
      '(()))))

And the result for (powerset('1 2 3)) is:

(NIL (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

But I can't use mapcar, and I cannot found the problem in my code, is there any alternative to the function mapcar?

Answer 1

Here is a possibile solution:

(defun parts (l)
  (if (null l)
      '(())
      (add (car l) (parts (cdr l)))))

(defun add (x pset)
  (if (null pset)
      nil
      (cons (car pset)
            (cons (cons x (car pset))
                  (add x (cdr pset))))))

(parts '(1 2 3))  ;   =>  (NIL (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))

The function add adds the element x to a powerset in this way:

1. if the powerset is empty, there is nothing to add;
2. otherwise, the new powerset is obtained by inserting or not the element in all the lists of the powerset, so by duplicating its number of lists.

The function parts builds recursively the powerset of a list, by adding, one of its elements at time, to the powerset constituted by a list containing the empty list (the powerset of the empty set).