3

I am trying to implement a powerset function in Scheme in two ways. One way is using tail recursion, and I did it like this:

(define (powerset list)
 (if (null? list) '(())                                    ;; if list is empty, its powerset is a list containing the empty list
  (let ((rest (powerset (cdr list))))                   ;; define "rest" as the result of the recursion over the rest of list
    (append (map (lambda (x) (cons (car list) x)) rest) ;; add the first element of list to the every element of rest (which is a sublist of rest) 
            rest))))                                    ;; and append it to rest itself (as we can either use the current element (car list), or not

Which works fine.

Another way is using foldr, and this is where I face some issues. My current implementation is as follows:

(define (powerset-fr list)
 (foldr (lambda (element result)        ;; This procedure gets an element (and a result);
       (if (null? result) ;; if starting with the empty list, there is nothing to "fold over".
           (cons '() (cons element result))
           (foldr (lambda (inner-element inner-result)
                    (append (cons element result) inner-result))
                  '(())
                  result)))
     '()                             ;; The result is initialized to the empty list,
     list))                         ;; and the procedure is being applied for every element in the first list (list1)

Which yields a poor result.

I'll try to explain shortly how did I approach this problem so far:

foldr runs over every element in the given set. For each such element, I should add some new elements to the powerset. Which elements should these be? One new element for each existing element in the powerset, where is append the current element in list to the existing element in powerset.

This is why I thought I should use foldr twice in a nested way - one to go over all items in given list, and for each item I use foldr to go over all items in "result" (current powerset).

I faced the problem of the empty list (nothing is being added to the powerset), and thus added the "if" section (and not just foldr), but it doesn't work very well either.

I think that's it. I feel close but it is still very challenging, so every help will be welcomed. Thanks!

avish12
  • 107
  • 8
  • 1
    It's a bad idea to call your variables and parameters `list`, `rest` - those are built-in procedures in some interpreters and you might have name clashes. – Óscar López Mar 18 '17 at 13:47
  • 1
    A fairly common naming convention is to use `xs` for a list of `x`, and `xss` for a list of lists of x. – soegaard Mar 18 '17 at 15:58
  • *"I thought I should use foldr twice in a nested way"* you were [exactly right](https://stackoverflow.com/a/65002298/849891), there. :) – Will Ness Nov 25 '20 at 16:25

1 Answers1

2

The solution is simpler, there's no need to use a double foldr, try this:

(define (powerset-fr lst)
  (foldr (lambda (e acc)
           (append (map (lambda (x) (cons e x)) 
                        acc) 
                   acc))
         '(())
         lst))

If your interpreter defines append-map or something equivalent, then the solution is a bit shorter - the results will be in a different order, but it doesn't matter:

(define (powerset-fr lst)
  (foldr (lambda (e acc)
           (append-map (lambda (x) (list x (cons e x)))
                       acc))
         '(())
         lst))

Either way, it works as expected:

(powerset-fr '(1 2 3))
=> '((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • 1
    Is it possible to do that using foldr without a direct recursion to `powerset-fr`? I mean, you can use recursion, but not to the main function that we are implementing.. – TomG Mar 25 '17 at 07:50
  • @TomG if not to the main function, to what, then? it won't be a recursion if you don't call the function itself! Anyway, the nature of the problem precludes it. – Óscar López Mar 25 '17 at 14:14
  • I meant that you can create a "helper" function that you can use recursion on it. But not to use recursion on the main function that we are implementing. Of course that no recursion at all would be great, but I guess it's not possible. – TomG Mar 25 '17 at 14:27
  • I don't think the fold is required to implement this and is only working due to coincidence. Power set is defined recursively $S = \{\} \implies P(S) = \{\{\}\}$, otherwise $e \in S$ and $T = S \ \{e\}$ then $P(S) = P(T) \cup \{t \cup \{e\} : t \in P(T)\}$. The fold is only returning the powerset defined recursively with the last $e$ in $lst$ removed, which coincidentally is the $(car lst)$. Therefore it just happens your function works. – notaorb Nov 22 '20 at 22:37
  • using `powerset-fr` defeats the purpose of using `foldr` which comes *instead* of direct explicit recursion. that's my first syntactical clue that something's wrong going on here. reading closer, this makes no sense to me at all. :) both snippet's combining functions make no use of their `acc` parameter. (????) so even though `foldr` does the recursion for the `(cdr lst)`, it throws away its result and redoes all the work by direct recursion. this use of foldr just replaces the cond. but then after throwing away the recursive result, it does the recursion anew! it must be **very slow**...... – Will Ness Nov 24 '20 at 17:18
  • .... much slower than necessary. it comes contrary to the spirit of it (i.e. that there won't be any use of direct recursion, and all recursion will be done through `foldr` only). so no, it does *not* qualify as `foldr`-based implementation of X, unfortunately. (in a lazy language the first recursion wouldn't be done, but Scheme is eager) – Will Ness Nov 24 '20 at 17:20
  • @WillNess you're right, thanks for pointing this out! I've updated my solution with your suggestion – Óscar López Nov 24 '20 at 21:50
  • @TomG yes, [it *is* possible](https://stackoverflow.com/a/65002298/849891). – Will Ness Nov 25 '20 at 16:22