   Powerset function in scheme (without map and lambda)
  This isn't a homework question. I'm self-studying HtDP (How to Design Programs) and I've spent the last week solving exercise 12.4.2 (creating a function that creates all of the permutations of a word). I had a lot of help from some of the people on the plt-scheme mailing list. Even though I finally found the solution, I wasn't confident that I understood the process enough in order to solve similar problems on my own.The problem I'm trying to solve now is to create a function which, given a set, provides as it's output the powerset of that set. (define (powerset set) ... )Given ... (powerset (list 'a 'b 'c))Expect ... (list (list 'b 'c) (list 'b) (list 'c) (list empty)  (list 'a 'b 'c) (list 'a 'b) (list 'a 'c) (list 'a))One of the tips I picked up from the plt-scheme list is to use a function "inventory" when designing functions. The inventory is just an explicit listing of the all the pieces of information available to you during a function call.For example:(powerset (list 'a 'b 'c)(first set) ... 'a(rest set) ... (list 'b 'c)(powerset (rest set)) ... (list (list 'b 'c) (list 'b) (list 'c) (list empty))and also right down the "right answer," or the answer that the function *should* be giving for the given input. In this case the right answer is:(list (list 'b 'c) (list 'b) (list 'c) (list empty) (list 'a 'b 'c) (list 'a 'b) (list 'a 'c) (list 'a))So, conceptually, (powerset (list 'a 'b 'c)) is just the value of the recursive call (powerset (list 'b 'c)), appended to the prepending of 'a to each list in (powerset (list 'b 'c). And there is a cool solution to this problem that uses map and lambda (and also let to reduce the function to only recursively calling powerset once, instead of twice), but I need to find the solution using only the topics that have been introduced up through chapter 13 in HtDP. That means, basically, I can use cons, cond, list, append, and any auxiliary functions I create cannot take more than two arguments.What I need is something like:(define (powerset set)   (cond   ((empty? set) (list (list empty)))  (else (append (powerset (rest set)) (prepend (first set) (powerset (rest set)))))))What I think I need is the right definition for prepend, but it's just not coming to me... I've been trying to put this together correctly for a couple days and I don't think I'm any closer now than I was when I started! Has anyone here solved this problem? Does anyone have any ideas on how to solve this problem?   
  (prepend first-element list-of-lists) needs to assemble a list-of-lists, where each list in the output is formed by putting first-element at the beginning of the corresponding input list. Let's say we have a function already that puts first-element at the beginning of a list. (Hint: We do.) To implement (prepend...) we need to call the function on the first list, and put the result of that at the beginning of the result of calling (prepend...) on the rest of the lists. (That's basically how (map...) works internally, BTW, although the compiler implementation might do some optimizations.)Hint: the way we "put something at the beginning of a list" is with (cons...). We do that at two points here: to assemble output lists, and to join the output lists to make the output list-of-lists.; Spoilers!(define (prepend first-element list-of-lists)   (cons (cons first-element (first list-of-lists))    (prepend first-element (rest list-of-lists))   )); should do it, I think. I'm a little rusty.;  That makes sense. I defined prepend as follows:; prepend:  symbol list-of-sets  ->  list-of-sets; creates a list-of-sets where sym is prefixed to each ; set in list-of-sets(define (prepend sym list-of-sets)  (cond    ((empty? list-of-sets) (list (list sym)))    (else (append (list (append (list sym) (first list-of-sets)))   (prepend sym (rest list-of-sets))))))Result of calling prepend:> (prepend 'a (list (list 'b 'c) (list 'j)))(list (list 'a 'b 'c) (list 'a 'j) (list 'a)).... seems to be working correctlyThe output from powerset is a bit off though, and I'm trying to figure out just why it's doing what it is. Here's the output from calling powerset on (list 'x 'y): > (powerset (list 'x 'y))(list (list empty)  (list 'y empty)  (list 'y)  (list 'x empty)  (list 'x 'y empty)  (list 'x 'y)  (list 'x))All of the subsets are there, plus it's creating duplicates (ie, (list 'y) and (list 'y empty) so instead of 2^n sets it's creating 2^n+((2^n)-1). But at least I'm a lot closer now than I was before! Thanks Zahlman!Note: Here's the full source of what I have so far, in case anyone wants to figure out where the extra lists are coming from ;-); a set is either; 1. empty or ; 2. (cons symbol set); a list-of-sets is either; 1. (cons empty empty) or; 2. (cons set list-of-sets); powerset:  set  ->  list-of-sets; creates the powerset of set, where each subset is a list(define (powerset set)  (cond    ((empty? set) (list (list empty)))    (else (append (powerset (rest set))   (prepend (first set) (powerset (rest set))))))); prepend:  symbol list-of-sets  ->  list-of-sets; creates a list-of-sets where sym is prefixed to each ; set in list-of-sets(define (prepend sym list-of-sets)  (cond    ((empty? list-of-sets) (list (list sym)))    (else (append (list (append (list sym) (first list-of-sets)))   (prepend sym (rest list-of-sets))))))(powerset (list 'x 'y))Edit: Changing ((empty? set) (list (list empty))) to just ((empty? set) empty) seems to have fixed the output...   