SICP Exercise 2.32

This is a real interesting one! I highly recommend working on it. I rank it up there with Exercise 1.11 in that once you get the answer, you’ll be amazed that the method really works. This is the kind of problem where functional programming really shines. All of the rules for it make the solution work out beautifully.

The end result, what should come out of the “subsets” function, comes from the classical mathematical notion of subsets. The set of subsets for a set contains at least two members: the original set itself, and the empty set. You see that in the example that’s given. Since order does not matter in a set, you don’t need to deal with repetitions, like (1 2) and (2 1). In fact, such repetitions should not show up in the result.

I’m not totally positive about this, but I think the way you achieve the answer has nothing to do with classical mathematics. Once again, I think this is solved using computing processes, not ones from classical mathematics. In that way it’s like Exercise 1.11 as well.

What I did to begin solving this was to look at the logic I was given, and do a walkthrough of it until I reached the point where I needed to fill in my own logic. I found it helpful to use the example set, and compare what I was getting to the expected result. As you back out of the recursion, look at what can be produced by using “map” with some logic that you think makes sense at each stage. And let your own logic evolve, if need be, to what you think you need to produce at each stage.

Happy programming!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s