power-set 
Author Message
 power-set

Hi,

    Who knows the power-set routine  in Scheme? I have several versions
in Lisp, but don't know how to translate it into Scheme.

Regards,
kitti

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Sat, 04 May 2002 03:00:00 GMT  
 power-set
+---------------
| Who knows the power-set routine  in Scheme? I have several versions
| in Lisp, but don't know how to translate it into Scheme.
+---------------

Translating simple functions from Common Lisp to Scheme is usually
fairly straightforward, e.g.:

        (defun foo (a b c) ...)     ==>  (define (foo a b c) ...)

        (defparameter foo init-val) ==>  (define foo init-val)

        (multiple-value-bind        ==>  (call-with-values
          (a b c) (some-mv-func)           some-mv-func
          ...body...)                      (lambda (a b c)
                                             ...body...)

        (mapcar #'func lists...)    ==>  (map func lists...)

        (mapc #'func lists...)      ==>  (for-each func lists...)

What part of the translation are you having trouble with?
Show us one of your Lisp versions and what you tried to
translate it into, and maybe we could help with that.

-Rob

-----

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



Sat, 04 May 2002 03:00:00 GMT  
 power-set
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.
(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)) ))

Thanks again,
kitti

Quote:
> Translating simple functions from Common Lisp to Scheme is usually
> fairly straightforward, e.g.:

>    (defun foo (a b c) ...)     ==>  (define (foo a b c) ...)

>    (defparameter foo init-val) ==>  (define foo init-val)

>    (multiple-value-bind        ==>  (call-with-values
>      (a b c) (some-mv-func)           some-mv-func
>      ...body...)                      (lambda (a b c)
>                                         ...body...)

>    (mapcar #'func lists...)    ==>  (map func lists...)

>    (mapc #'func lists...)      ==>  (for-each func lists...)

> What part of the translation are you having trouble with?
> Show us one of your Lisp versions and what you tried to
> translate it into, and maybe we could help with that.

> -Rob

> -----

> 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

Sent via Deja.com http://www.deja.com/
Before you buy.


Sat, 04 May 2002 03:00:00 GMT  
 power-set

Quote:

> 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.
> (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)) ))

;; less goofy syntax _and_ shorter
;; could be shorter still by putting '(()) for (list '())

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

--

Programmer in Chief, Free Computer Shop <http://www.free-comp-shop.com>
         ---  Food, Shelter, Source code.  ---



Sat, 04 May 2002 03:00:00 GMT  
 power-set
+---------------
| 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)))))
        >

-----

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



Sun, 05 May 2002 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Set of power sets

2. challenge: set partitions and power set

3. recursive routine for power set ?

4. Prunning your way through a power set

5. power set

6. I wanna make power-set ....

7. power set function

8. power set implementation?

9. powerset again

10. Powerset Predicate

11. Powersets code

12. Question: Powersets code?

 

 
Powered by phpBB® Forum Software