Generating powerset in one function, no explicit recursion, and using only simplest primitives in Racket

Question

Note: this is a bonus for homework, but I have spent way too long on trying things to no avail. Help is much appreciated, but not necessary I suppose.

Premise: generate a powerset for a list of numbers, but without using any helpers, explicit recursion, looping, or functions/constants other than cons, first, rest, empty?, empty, else, lambda, and cond, while using only one define on the language level Intermediate Student with Lambda. The order of the powerset does not matter.

What I've tried so far: I have discovered the Y-combinator and anonymous recursion thanks to this post (author has the same end goal but we have different approaches, so the information in his post does not solve my problem), and the powerset code in this answer, and with that I have written the following:

(define (powerset aL)
  (((lambda (X)
      ((lambda (proc)
         (proc proc))
       (lambda (proc)
         (X (lambda (arg)
              ((proc proc) arg))))))
    (lambda (subset)
      (lambda (lst)
        (cond
          [(empty? lst) (list empty)]
          [else (combine (first aL) (powerset (rest aL)))])))) aL)

(define (combine a r)
  (cond
    [(empty? r)  empty]
    [else (cons (cons a (first r)) (cons (first r) (combine a (rest r))))]))

I'm testing this code by running:

(check-expect (powerset '(1 2 3)) 
(list '(1 2 3) '(2 3) '(1 3) '(3) '(1 2) '(2) '(1) '()))

This code runs and produces a correct result, but, as you can see, I still rely on an external helper function, combine, and I have no idea how to convert that into a lambda since to my knowledge, the Y-combinator only works with one parameter and combine needs 2. Perhaps my logic or approach to this problem is flawed. I have limited experience with lambda so I could be missing knowledge as well.

What I need help with: any suggestions as to next steps, helping me intergrate combine into powerset, providing hints/clues to correct logic/approach, or a solution would be much appreciated.

Thanks in advance!

Generally if you have solved your problem, you should say so with the Answer button: comments are not for answers. It's acceptable (even encouraged!) to answer your own questions. Just write the Answer that you would have liked to see someone else write. — amalloy, Nov 19 '20 at 05:50
I'm curious, did you get your original `powerset` code (the one before the conversion with the Y combinator) from [this answer](https://stackoverflow.com/a/20623487/849891), or from somewhere else? (the transformation is wrong, BTW, the function set up by Y is not used, instead `powerset` is called by explicit recursion). — Will Ness, Nov 19 '20 at 17:31
@amalloy professors are strict about code sharing, I'll share the code after the assignment is due! — , Nov 20 '20 at 06:06
Yes, I did take the logic from there since my original solution used `foldr` and `map` which would have been harder to replicate using anonymous recursion. I also realized that my code was using explicit recursion when writing the final version, I have corrected that mistake and the final code uses anonymous recursion with `lambda` only. Thanks for all the tips and answers! — , Nov 20 '20 at 06:09

score 4 · Answer 1 · answered Nov 19 '20 at 03:44

the Y-combinator only works with one parameter and combine needs 2

Any multi-argument function can be imagined as a one-argument function, returning a lambda that waits for the next argument. This process is called currying. For example, if we have

(define add (x y)
  (+ x y))

we could call it like

(add 2 2)

Simple enough. Now let's curry it:

(define (add x)
  (lambda (y)
    (+ x y)))

Calling it takes a slightly different syntax, but it's the same basic idea:

((add 2) 2)

You can apply the same concept to any lambda if you wish to make it suitable to the Y combinator.

score 2 · Answer 2 · edited Dec 03 '20 at 18:37

In lambda calculus, all functions are curried unary functions.

This means

(define (combine a r)
  (cond
    [(empty? r)  empty]
    [else (cons (cons a (first r))
                (cons (first r) 
                      (combine a (rest r))))]))

would be written as

(λ (combine)
  (λ (a)
    (λ (r)
      (cond
        [(empty? r) empty]
        [else (cons (cons a (first r))
                    (cons (first r) 
                          ((combine a) (rest r))))]))))

With this in mind, here is the solution:

(define powerset
  ((λ (y)
     ((λ (f) (y (λ (x) ((f f) x))))
      (λ (f) (y (λ (x) ((f f) x))))))
   
   (λ (ps)
     (λ (set)
       (cond
         [(empty? set) (cons empty empty)]
         [else ((((λ (y)
                    ((λ (f) (y (λ (x) ((f f) x))))
                     (λ (f) (y (λ (x) ((f f) x))))))
                  
                  (λ (combine)
                    (λ (a)
                      (λ (r)
                        (cond
                          [(empty? r) empty]
                          [else (cons (cons a (first r))
                                      (cons (first r) 
                                            ((combine a) (rest r))))])))))
                 (first set))
                (ps (rest set)))])))))

"`(define (combine a r) ...)` would be written as" `(` **`Y`** `(λ (combine) (λ (a) (λ (r) .... ))))`, though. as you indeed do, later in the answer. :) — Will Ness, Dec 03 '20 at 18:39

score 1 · Accepted Answer · edited Nov 19 '20 at 16:55

I find the trick below easier to understand than using Y. I think it's sort of related to U (which I also find easier to understand than Y).

It's possible that this isn't enough to meet the requirement of 'not being explicitly recursive', although I think it is.

If you have some function which 'wants' to use itself freely so it can recurse, such as:

(define powerset
  (λ (set)
    (cond [(empty? set)
           (list empty)]
          [else
           (combine (first set)
                    (powerset (rest set)))])))

Then you can turn that into a function which takes an additional argument, which it calls:

(define powerset/c
  (λ (ps/c set)
    (cond [(empty? set)
           (list empty)]
          [else
           (combine (first set)
                    (ps/c ps/c (rest set)))])))

The /c names are because when I discovered this trick I was thinking about the argument as a continuation, but I think that's because I didn't know what continuations were really.

And now (with a definition for combine), (powerset/c powerset/c '(x y z)) will compute the power set of (x y z), and there is no explicit recursion.

Well, that's ugly but this is easy to fix using

(define powerset
  (λ (set)
    ((λ (powerset/c)
       (powerset/c powerset/c set))
     (λ (ps/c set)
       (cond [(empty? set)
              (list empty)]
             [else
              (combine (first set)
                       (ps/c ps/c (rest set)))])))))

Then the trick is to write combine this way as well, and then use it locally, with

(define powerset
  (λ (set)
    ((λ (combine)
       ((λ (powerset/c)
          (powerset/c powerset/c set))
        (λ (ps/c set)
          (cond [(empty? set)
                 (list empty)]
                [else
                 (combine (first set)
                          (ps/c ps/c (rest set)))]))))
     <combine defn here>)))

yeah the whole purpose of **Y** is to spare one having to write `(f f x)` explicitly for a recursive call, nothing more (I think). too bad they don't say as much in the books, making it so complex instead, when it is really pretty simple. — Will Ness, Nov 19 '20 at 17:08
[this answer](https://stackoverflow.com/a/8344517/849891) on the entry linked by OP in the Q, presents the same idea nicely. — Will Ness, Nov 19 '20 at 17:54

Generating powerset in one function, no explicit recursion, and using only simplest primitives in Racket

3 Answers3

Linked