Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:

(define (powerset set-list) (if (null? set-list) '(()) (let* ((powerset-of-smaller-set (powerset (cdr set-list))) (delta (map (lambda (e) (cons (car set-list) e)) powerset-of-smaller-set))) (append powerset-of-smaller-set delta))))

This function illustrates the real power of recursion. Assuming that we can calculate the powerset of S minus its first element, the powerset of S is obtained by adding a systematic combination of the first element with each and every set in the smaller powerset.

The solution is inspired directly from Christian Wagenknecht's book 'Programmierparadigmen', from Springer Verlag.