<vivideja@my-deja.com> wrote:
+---------------
| Thank you for getting back to me. Following is a version of
| power-set in Lisp and I don't quite understand how to translate.
+---------------

Hmmm... I can see why; there's a goodly amount of "Lispiness" in there.
O.k., I'll help translate, but I'm going to try to leave the algorithm
unexplained so you have something to learn for yourself, all right?

+---------------
| (defun power-set (s)
|   (cond (s (let ((a (car s))
|                 (b (power-set (cdr s))))
|             (nconc (loop for x in b
|                           collect (cons a x))
|                     b)))
|         (T (list nil)) ))
+---------------

Let's take this in steps:

0. As noted in my previous reply, in Scheme the outer definition
   should read:  (define (power-set s) ...)

1. Boolean "truth" is slightly different in Scheme & CL. In Scheme,
   *only* "#f" is false, and everything else *including* the empty
   list "()" is true [and the symbol "nil" is just another ordinary
   symbol with no predefined meaning]. Whereas in CL, the symbol "nil"
   is identical to boolean false is identical to the empty list, which
   allows a kind of type punning that's not permitted in Scheme. So
   whenever you see a boolean test in CL such as in the outer "cond",
   you have to ask yourself, "Is this code testing for what is logically
   a 'false boolean value' or for an 'empty list'?"

   In the above code, we see that "car" & "cdr" are applied to "s",
   so "s" is almost certainly intended to represent a list, not a
   boolean variable per se. So let's convert the "cond" to read as
   follows (also changing the default branch from "t" to "else", per
   Scheme style):

	(define (power-set s)		; caveat: incomplete translation
	  (cond
	    ((not (null? s))		; see note [*]
	     (let ((a (car s))
		   (b (power-set (cdr s))))
               (nconc (loop for x in b
                            collect (cons a x))
                      b)))
             (else (list nil))))

2. The CL function "nconc" is a (potentially) side-effecting version
   of "append". Standard Scheme doesn't contain such a thing, but many
   individual implementions do, and call it "append!". However, the
   difference turns out not to matter to the algorithm here, and the
   subtleties of when mutating operators are faster/better than functional
   (non-mutating) operators [e.g., especially in the presence, say, of
   copying generational GCs] are way beyond the scope of this discussion,
   so I'll just translate "nconc" here to "append".

3. The "(loop for x in b collect (cons a x))" is more troublesome, since
   CL's "loop" is a *very* complex topic, and I'd rather not go down that
   particular rat hole. Besides, I'm afraid that explaining it in detail
   would also spoil your learning something yourself from the algorithm.

   Fortunately, in this particular instance, the "collect" sub-form of the
   "loop" is being used for something that maps [if you'll pardon the pun!]
   very nicely onto a functional Scheme construct, which I'm going to give
   you without further explanation: (map (lambda (x) (cons a x)) b)

   Figuring out what *that* does will give you insights into the algorithm
   of "power-set".

4. Finally, let's replace that "nil" in the default branch with the
   Scheme empty list (quoted, as required by the standard, though not
   needed by some implementions).

Put it all together, and you get:

	> (define (power-set s)
	    (cond
	      ((not (null? s))
	       (let ((a (car s))
		     (b (power-set (cdr s))))
		 (append (map (lambda (x) (cons a x)) b)
			 b)))
	       (else (list '()))))
	> 

Since we've decided that "s" must be a list, we should be able to test it
by handing it lists of things:

	> (power-set '(joe bob bill))
	((joe bob bill) (joe bob) (joe bill) (joe) (bob bill) (bob) (bill) ())
	> (power-set '(a b c d))
	((a b c d) (a b c) (a b d) (a b) (a c d) (a c) (a d) (a) (b c d)
	 (b c) (b d) (b) (c d) (c) (d) ())
	> 

Your turn...  ;-}


-Rob

[*] Yes, I know that the test "(not (null? s))" could be written slightly
    faster [probably] as "(pair? s)", but IMHO the latter is conceptually
    less clear. Better still would be to re-order the whole "cond" with
    the base case first:

	> (define (power-set s)
	    (cond
	      ((null? s)
	       (list '()))
	      (else
	       (let ((a (car s))
		     (b (power-set (cdr s))))
		 (append (map (lambda (x) (cons a x)) b)
			 b)))))
	> 

-----
Rob Warnock, 8L-846		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		FAX: 650-933-0511
Mountain View, CA  94043	PP-ASEL-IA