list - Subset / Subsequence Recursive Procedure in Simply Scheme Lisp

Question

I am working my way through Simply Scheme in combination with the Summer 2011 CS3 Course from Berkley. I am struggling with my understanding of the subset / subsequence procedures. I understand the basic mechanics once I'm presented with the solution code, but am struggling to grasp the concepts enough to come up with the solution on my own.

Could anyone point me in the direction of something that might help me understand it a little bit better? Or maybe explain it differently themselves?

This is the basis of what I understand so far:

So, in the following procedure, the subsequences recursive call that is an argument to prepend, is breaking down the word to its basest element, and prepend is adding the first of the word to each of those elements.

; using words and sentences

(define (subsequences wd)
  (if (empty? wd)
      (se "")
      (se (subsequences (bf wd))
          (prepend (first wd) 
                   (subsequences (bf wd))))))

(define (prepend l wd)
  (every (lambda (w) (word l w))
         wd))

; using lists

(define (subsequences ls)
  (if (null? ls)
      (list '())
      (let ((next (subsequences (cdr ls))))
        (append (map (lambda (x) (cons (car ls) x))
                     next)
                next)))) 

So the first one, when (subsequences 'word) is entered, would return:

    ("" d r rd o od or ord w wd wr wrd wo wod wor word)

The second one, when (subsequences '(1 2 3)) is entered, would return:

    ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())

So, as I said, this code works. I understand each of the parts of the code individually and, for the most part, how they work with each other. The nested recursive call is what is giving me the trouble. I just don't completely understand it well enough to write such code on my own. Anything that might be able to help me understand it would be greatly appreciated. I think I just need a new perspective to wrap my head around it.

Thanks in advance for anyone willing to point me in the right direction.

EDIT:

So the first comment asked me to try and explain a little more about what I understand so far. Here it goes:

For the words / sentence procedure, I think that it's breaking the variable down to it's "basest" case (so to speak) via the recursive call that appears second.

Then it's essentially building on the basest case, by prepending.

I don't really understand why the recursive call that appears first needs to be there then.

In the lists one, when I was writing it on my own I got this:

(define (subseq lst)
  (if (null? lst)
      '()
      (append (subseq (cdr lst))
              (prepend (car lst)
                       (subseq (cdr lst))))))

(define (prepend i lst)
  (map (lambda (itm) (cons i itm)) 
       lst))

With the correct solution it looks to me like the car of the list would just drop off and not be accounted for, but obviously that's not the case. I'm not grasping how the two recursive calls are working together.

Answer 1

Your alternate solution is mostly good, but you've made the same mistake many people make when implementing this (power-set of a list) function for the first time: your base case is wrong.

How many ways are there to choose a subset of 0 or more items from a 0-element list? "0" may feel obvious, but in fact there is one way: choose none of the items. So instead of returning the empty list (meaning "there are no ways it can be done"), you should return (list '()) (meaning, "a list of one way to do it, which is to choose no elements"). Equivalently you could return '(()), which is the same as (list '()) - I don't know good Scheme style, so I'll leave that to you.

Once you've made that change, your solution works, demonstrating that you do in fact understand the recursion after all!

---

As to explaining the solution that was provided to you, I don't quite see what you think would happen to the car of the list. It's actually very nearly the exact same algorithm as the one you wrote yourself: to see how close it is, inline your definition of prepend (that is, substitute its body into your subsequences function). Then expand the let binding from the provided solution, substituting its body in the two places it appears. Finally, if you want, you can swap the order of the arguments to append - or not; it doesn't matter much. At this point, it's the same function you wrote.