Combinations of list elements

Question

It was written in Emacs Lisp and requires Common Lisp loop facility.

Can this code be improved? Did I hit any anti-patterns along the way?

(defun combos (list)
 (let* ((a (car list))
 (d (cdr list))
 (s (and d (combos d)))
 (v (loop for c in s collect (cons a c))))
 (cons (list a) (append s v))))

Answer 1

I would suggest handling a nil input explicitly. Then you can:

• strip out the and (in s's binding), and just recurse directly
• strip out the cons at the bottom, leaving only the append

Here's the code I tested with (in Scheme, since I have neither Emacs nor a CL implementation installed):

;; Requires SRFI 26
(define (combos lst)
 (if (null? lst) '(())
 (let* ((a (car lst))
 (d (cdr lst))
 (s (combos d))
 (v (map (cut cons a <>) s)))
 (append s v))))

And if you really can't bear to see the empty list as one of the combinations (though it really is), just take the cdr of the resulting list. It's always the first element.

---

Update: I installed Emacs now, so I was able to port my Scheme version to elisp and test it:

(defun combos (list)
 (if (null list) '(nil)
 (let* ((a (car list))
 (d (cdr list))
 (s (combos d))
 (v (mapcar (lambda (x) (cons a x)) s)))
 (append s v))))

• Gareth Rees: Elisp is a Lisp2, so there's no need to misspell list as lst just to avoid shadowing the built-in function.
• C. K. Young: @GarethRees Of course. But I'm a Schemer, and Scheme habits die hard. Like the tendency to want to do everything with a named let or syntax-case macros. ;-)

Answer 2

Two important problems:

1. Your function could be better named: it returns a list of the non-empty subsets of its argument, so it should be called something like non-empty-subsets.

2. There's no docstring.

I think the most natural way to implement this function is to implement subsets (which is straightforward) and then drop the empty subset:

(defun subsets (list)
 "Return a list of the subsets of LIST."
 (if (null list) '(nil)
 (let ((e (car list))
 (ss (subsets (cdr list))))
 (append ss (loop for s in ss collect (cons e s))))))
(defun non-empty-subsets (list)
 "Return a list of the non-empty subsets of LIST."
 (cdr (subsets list)))

But tastes differ, so you might legitimately prefer your original version.

• C. K. Young: Very succinct. I like.