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.

Answer 2

Recursion is a tool which is there to help us, to make programming easier.

A recursive approach doesn't try to solve the whole problem at once. It says, what if we already had the solution code? Then we could apply it to any similar smaller part of the original problem, and get the solution for it back. Then all we'd have to do is re-combine the leftover "shell" which contained that smaller self-similar part, with the result for that smaller part; and that way we'd get our full solution for the full problem!

So if we can identify that recursive structure in our data; if we can take it apart like a Russian "matryoshka" doll which contains its own smaller copy inside its shell (which too contains the smaller copies of self inside itself, all the way down) and can put it back; then all we need to do to transform the whole "doll" is to transform the nested "matryoshka" doll contained in it (with all the nested dolls inside -- we don't care how many levels deep!) by applying to it that recursive procedure which we are seeking to create, and simply put back the result:

    solution( shell <+> core )   ==   shell  {+}  solution( core )
;;            --------------                                ----

The two +s on the two sides of the equation are different, because the transformed doll might not be a doll at all! (also, the <+> on the left is deconstructing a given datum, while {+} on the right constructs the overall result.)

This is the recursion scheme used in your functions.

Some problems are better fit for other recursion schemes, e.g. various sorts, Voronoi diagrams, etc. are better done with divide-and-conquer:

    solution( part1 <+> part2 )   ==   solution( part1 ) {+} solution( part2 )
;;            ---------------                    -----                 -----

As for the two -- or one -- recursive calls, since this is mathematically a function, the result of calling it with the same argument is always the same. There's no semantic difference, only an operational one.

Sometimes we prefer to calculate a result and keep it in memory for further reuse; sometimes we prefer to recalculate it every time it's needed. It does not matter as far as the end result is concerned -- the same result will be calculated, the only difference being the consumed memory and / or the time it will take to produce that result.